有序数组双指针问题

问题 1： 有序数组使用双指针快速搜索

我们以 力扣167. 两数之和 II - 输入有序数组 为例对该问题进行求解

步骤 1 ：分析并使用双指针

1、重要信息：numbers已经“非递减顺序排列”！！！！，我们一定要利用这个信息。
2、我们将双指针分别指向数组的头和尾，如果此时头尾数的和比target大，因为数组是非递减排序，并且我此时需要一个更大的数，所以我们只需要将左指针右移，此时和必然会增加。
3、如果此时头尾数的和比target小，同理，我们只需要将右指针左移，就可以减小两个数的和。
4、用以上的办法逐渐进行逼近，直到逼近到正确的双指针位置。

步骤 2 ：实现

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int i = 0, j = n - 1;//双指针初始化
        while (i < j) {
            if (numbers[i] + numbers[j] == target) {//因为答案要从1开始
                return { i + 1,j + 1 };
            }
            else if (numbers[i] + numbers[j] > target) {
                j--;
            }
            else {
                i++;
            }
        }
        return {};
    }
};

注意

值得注意的是，以上双指针解法的前提都是，随着左右指针的移动，两数之和能严格增长或者下降，也就是满足数组的非递减特性才可以这么做。

问题 2： 变种问题（三数之和）

我们以 力扣15. 三数之和 为例对该问题进行求解

步骤 1 ：分析并排序

由题意可知，nums是一个乱序的数组，并且最终的答案和数组中原本的顺序是无关的，所以这种题，第一反应必须是：：排序。
因为数据顺序不影响答案，所以执行排序，这样重整之后，更方便我们选择合适的算法

步骤 2 ：分析并使用双指针

1、我们观察：nums[i] + nums[j] + nums[k] = 0。切记一旦发现左侧是个常数C的时候，我们就要将之视作一个“空位”，所以要将左式中的一个变量移动到空位这边，这种转换思路一定要会。其实所谓难题，就是基础模板之上添加了许多转换。
2、当问题转化成，找到合适的i、j、k，让nums[j] + nums[k] = -nums[i]，很明显，就是问题1，只不过我们需要在最外层加一个遍历i就可以了。
3、注意，题目中要求，不能出现重复答案，也就是说，当指针遇到重复元素的时候，我们一定要跳过，要不肯定会出现重复元素。

步骤 3 ：优化

1、当nums[i] + nums[i+1] + nums[i+2] > 0 时候，这代表了有序数组最左侧最小的三个元素和都是大于0的，所以以后必不可能出现=0的情况，直接结束。
2、当nums[i]+ nums[n-1] + nums[n-2] < 0 时候，说明当前这个nums[i]不可能会存在答案，但是之后可能会有答案，所以我们跳过。

步骤 4 ：实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i && x == nums[i - 1]) {//当遇到重复元素，这个nums[i]就是无效的，继续循环
                continue;
            }
            if (x + nums[i + 1] + nums[i + 2] > 0) {//优化
                break;
            }
            if (x + nums[n - 1] + nums[n - 2] < 0) {//优化
                continue;
            }
            int j = i + 1, k = n - 1;//开始双指针
            while (j < k) {
                if (x + nums[j] + nums[k] > 0) {
                    k--;
                }
                else if (x + nums[j] + nums[k] < 0) {
                    j++;
                }
                else {
                    ans.push_back({ x,nums[j],nums[k] });
                    //找到一个答案后，可能还存在多个，所以j++\k--，继续按照规则找，记得跳过重复元素
                    j++;
                    while (j < k && nums[j] == nums[j - 1]) {//跳过重复元素
                        j++;
                    }
                    k--;
                    while (k > j && nums[k] == nums[k + 1]) {//跳过重复元素
                        k--;
                    }
                }
            }
        }
        return ans;
    }
};