欢迎访问LeetCode题解合集

题目描述

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]

提示：

• 2 <= numbers.length <= 3 * 10^4

• -1000 <= numbers[i] <= 1000

• numbers 按 递增顺序 排列

• -1000 <= target <= 1000

• 仅存在一个有效答案

题解：

双指针。

设两个指针 i 和 j 分别指向数组首尾元素，然后根据 t = nums[i] + nums[j] 与 target 的大小关系讨论：

• t > target ，说明 t 太大了，应该减小它的值，于是 j--
• t < target ，说明 t 太小了，应该增加它的值，于是 i++
• t == target ，说明找到了答案，直接返回即可

时间复杂度：$O(n)$

额外空间复杂度：$O(1)$

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0, j = numbers.size() - 1, t;
        while ( i < j ) {
            t = numbers[i] + numbers[j];
            if( t == target ) return {i + 1, j + 1};
            if( t < target ) ++i;
            else --j;
        }
        return {};
    }
};
/*
时间：4ms，击败：93.74%
内存：9.2MB，击败：91.16%
*/