题目链接

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

题目描述

在一个非递减顺序排列的数组中，找出两个数的下标满足：两个下标对应的数字之和等于目标值。

假定只有唯一解，且数字不能重复使用。

输入输出样例

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

题目解释

双指针，第一个指针指向开头，第二个指针指向结尾，

如果两个指针指向的数字比目标值大，右指针左移

如果两个指针指向的数字比目标值小，左指针右移

代码

个人实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 暴力解法：超时
// 双指针，第一个指针固定，第二个指针顺位移动，如果两个指针指向的数字比目标值大
// 两个指针向右移动，重复过程。
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> ans;
        for (int i = 0; i < numbers.size() - 1; i++) {
            int j = i + 1;
            while (numbers[i] + numbers[j] < target) {
                j++;
                if (j == numbers.size()) {
                    break;
                }
            }
            if (j == numbers.size()) {
                continue;
            }
            if (numbers[i] + numbers[j] == target) {
                return {i + 1, j + 1};
            }
        }
        return ans;
    }
};

// 正常双指针解法
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        int value = 0;
        while (l < r) {
            value = numbers[l] + numbers[r];
            if (value == target)
                return {l + 1, r + 1};
            value < target ? l++ : r--;
        }
        return {};
    }
};

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/solutions/337156/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leet-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0, high = numbers.size() - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return {low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return {-1, -1};
    }
};