本周，着重完成双指针部分的内容，今天结合15.三数之和，整理一下双指针能解决的问题。

首先，双指针能解决某些交换问题，此类问题较为灵活，应针对题目思考解决，例如283.移动零，这道题利用双指针将非零值换到数组左侧。

其次，双指针能结合排序，解决数组中两数相加为某个定值的问题——将此类问题的规模从O（n²）转化为O（nlogn），包括15.三数之和也是这类的问题。

面对数组中两数相加为定值的问题，很容易想到利用二重循环进行遍历，此时时间复杂度为O（n²）。

若利用双指针的思路，首先将数组进行排序，排序算法（如快排等）时间复杂度均为O（nlogn），然后将两个指针分别放在这个数组的两侧，如果结果偏大，右指针左移，结果偏小，左指针右移，此时，整个数组仅需遍历一次。

在15.三数之和中，先假设确定第一个值，就转化为了两数和为定值的问题，总的复杂度由O(n³)降低到O（n²），代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        for(int i=0;i<nums.size()-2;i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue;
            int k=nums.size()-1;
            for(int j=i+1;j<nums.size()-1;j++)
            {
                
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                while(nums[i]+nums[j]+nums[k]>0&&k>j) k--;
                if(k<=j) break;
                if(nums[i]+nums[j]+nums[k]==0)
                {
                    ans.push_back({nums[i],nums[j],nums[k]});
                    continue;
                }
            }
        }
        return ans;
    }
};

再贴一个leetcode的官方代码（带注释）：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/3sum/solutions/284681/san-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。