LeetCode 每日一题 167. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组

难度中等

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目描述：在有序数组中找出两个数，使它们的和为 target。

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

• 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
• 如果 sum > target，移动较大的元素，使 sum 变小一些；
• 如果 sum < target，移动较小的元素，使 sum 变大一些。

代码:

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0, j = numbers.size() - 1; i < numbers.size(); i++)
        {
            while(i < j && (numbers[i] + numbers[j] > target)) j--;
            
            if (numbers[i] + numbers[j] == target)
                {
                    return {i + 1, j + 1};
                }
        }
        return {-1, -1};
    }
};

代码模板

双指针:

for (int i = 0, j = 0; i < n; i ++)
{
    while (j < i && check(i, j)) j ++;

    // 具体问题的逻辑
}
常见问题分类
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作