双指针算法：三数之和与四数之和问题求解

时间复杂度：O(n^2)，空间复杂度：O(logn)。

1.4 过程推算

本题整个的思路、算法原理、解题过程推导如下：

1.5 反思

总结：

1、熟悉 STL 容器用法，如 vector<vector<int>> 和 push_back； 2、注意边界优化，如 nums[i] <= 0 的判断； 3、去重操作位置关键，left 和 right 在循环内去重，i 在循环外移动后去重； 4、时间复杂度：O(n^2)，for 循环嵌套一个 while 循环； 5、空间复杂度：O(logn)，主要是排序占用的栈空间。

008 四数之和

题目描述：

2.1 题目解析

如下所示：

2.2 思路 1：暴力

解法一：暴力求解（会超时）

参考上面的【三数之和】逻辑扩展：

2.3 思路 2：排序 + 双指针

2.3.1 算法思路

1、依次固定一个数 a； 2、在这个数 a 的后面区间上，利用【三数之和】找到三个数，使这三个数的和等于 target - a 即可。这里有两个区间，大的区间里面固定一个数 b，小的区间里面定义一个 left 和 right 两个下标指针，里面的两数之和，加上 a 和 b，加起来和 target 比。

2.3.2 代码实现

代码演示：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        // 1、排序
        sort(nums.begin(), nums.end());
        // 2、固定 i
        int n = nums.size();
        for (int i = 0; i < n;) {
            // 固定 j
            for (int j = i + 1; j < n;) {
                // 3、双指针
                int left = j + 1, right = n - 1;
                while (left < right) {
                    long sum = (long)nums[left] + nums[right];
                    long tmp = (long)nums[i] + nums[j];
                    if (sum > (target - tmp)) right--;
                    else if (sum < (target - tmp)) left++;
                    else {
                        ret.push_back({nums[i], nums[j], 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--;
                    }
                }
                // j 查重，j 移动
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // i 查重，i 移动
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

时间复杂度：O(n^3)，空间复杂度：O(logn)。

2.4 过程推算

本题整个的思路、算法原理、解题过程推导如下：

2.5 反思

1、整体思路正确、逻辑没问题； 2、注意整数溢出问题，大数相加时变量类型应改为 long 或进行强制类型转换； 3、掌握 STL 容器的使用技巧。