【算法专题--双指针算法】leecode-15.三数之和（medium）、leecode-18. 四数之和（medium）

---

---

---

---

前言

• 对撞指针从两端向中间移动。一个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
• 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
• • left == right （两个指针指向同一个位置）
• • left > right （两个指针错开）

快慢指针的实现方式有很多种，最常用的⼀种就是：

• 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

---

1. 三数之和

题目描述：

示例 1：

示例 2：

示例 3：

提示：

2. 解法（排序+双指针）：

算法思路：

本题与两数之和类似，是非常经典的面试题。
与两数之和稍微不同的是，题目中要求找到所有「不重复」的三元组。那我们可以利用在两数之和那里用的双指针思想，来对我们的暴力枚举做优化：

1. 先排序；
2. 然后固定⼀个数 a ：
3. 在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于 -a 即可。

但是要注意的是，这道题里面需要有「去重」操作~

1. 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
2. 当使用完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素

算法流程：

先将 nums 排序，时间复杂度为 O(NlogN)。

固定 333 个指针中最左（最小）元素的指针 k，双指针 i，j 分设在数组索引 (k,len(nums))(k, len(nums))(k,len(nums)) 两端。

双指针 iii , jjj 交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：

1. 当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 3 个元素都大于 0 ，在此固定指针 k 之后不可能再找到结果了。
2. 当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
   3.i，j分设在数组索引 (k,len(nums))两端，当i < j时循环计算sum = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：

• 当s < 0时，i += 1并跳过所有重复的nums[i]；

• 当s > 0时，j -= 1并跳过所有重复的nums[j]；

• 当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合。

C++代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n;) // 固定数 a
        {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) 
            {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else 
                {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++, right--;
                    // 去重操作 left 和 right
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重 i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

Java代码：

class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) // 固定数 a
        {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else
                {
                    // nums[i] nums[left] num[right]
                     ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                     left++; right--; // 缩⼩区间继续寻找
                     // 去重：left right
                     while (left < right && nums[left] == nums[left - 1]) left++;
                     while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重：i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
}

3. 四数之和（medium）

题目描述：

示例 1：

示例 2：

提示：

4. 解法（排序 + 双指针）

前置题目:
请先完成三数之和。

思路:
思路和三数之和 一样，排序后，枚举 nums[a]作为第一个数，枚举 nums[b] 作为第二个数，那么问题变成找到另外两个数，使得这四个数的和等于 target，这可以用双指针解决。
对于 nums[a] 的枚举：

1. 设 s=nums[a]+nums[a+1]+nums[a+2]+nums[a+3]。如果 s>targets，由于数组已经排序，后面无论怎么选，选出的四个数的和不会比 s 还小，所以后面不会找到等于 target的四数之和了。所以只要 s>targets ，就可以直接 break 外层循环了。

2. 设 s=nums[a]+nums[n−3]+nums[n−2]+nums[n−1]。如果 s<targets ，由于数组已经排序，nums[a]加上后面任意三个数都不会超过 s，所以无法在后面找到另外三个数与 nums[a]相加等于 target。但是后面还有更大的 nums[a]，可能出现四数之和等于 target 的情况，所以还需要继续枚举，continue 外层循环。

3. 如果 a>0且 nums[a]=nums[a−1]，那么 nums[a] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue 外层循环。（可以放在循环开头判断。）

对于 nums[b] 的枚举（b 从 a+1 开始），也同样有类似优化：

1. 设 s=nums[a]+nums[b]+nums[b+1]+nums[b+2]。如果 s>targets，由于数组已经排序，后面无论怎么选，选出的四个数的和不会比 s 还小，所以后面不会找到等于 target 的四数之和了。所以只要 s>targets ，就可以直接 break。

2. 设 s=nums[a]+nums[b]+nums[n−2]+nums[n−1]。如果 s<targets，由于数组已经排序，nums[a]+nums[b] 加上后面任意两个数都不会超过 s，所以无法在后面找到另外两个数与 nums[a] 和 nums[b] 相加等于 target。但是后面还有更大的 nums[b]，可能出现四数之和等于 target 的情况，所以还需要继续枚举，continue。

3. 如果 b>a+1b>a+1b>a+1 且 nums[b]=nums[b−1]，那么 nums[b]\textit{nums}[b]nums[b] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue。注意这里 b>a+1 的判断是必须的，如果不判断，对于示例 2 这样的数据，会直接 continue，漏掉符合要求的答案。

对于 Java/C++ 等语言，注意相加结果可能会超过 32 位整数范围，需要用 64 位整数存储四数之和。

C++代码：

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 利⽤ 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim) left++;
                    else if (sum > aim) right--;
                    else
                    {
                        ret.push_back({ nums[i], nums[j], nums[left++],
                       nums[right--] });
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

Java代码：

class Solution
{
    public List<List<Integer>> fourSum(int[] nums, int target)
    {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long aim = (long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > aim) right--;
                    else if (sum < aim) left++;
                    else
                    {
                        ret.add(Arrays.asList(nums[i], nums[j], nums[left++],
                            nums[right--]));
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
}