【双指针】专题：LeetCode 18题解——四数之和

一、题目链接

四数之和

二、题目

三、题目解析

题目要求基本与三数之和一样。

四、算法原理

解法几乎照搬三数之和

解法一：排序 + 暴力枚举 + 利用 set 去重

绝对超时，时间复杂度是O(n^4)。

解法二：排序 + 双指针

示例1排好序：

步骤：

1. 排序
2. 从左向右依次固定一个数a
3. 在a的右区间内，利用"三数之和"找到三个数，使这三个数之和等于target - a即可：从左向右依次固定一个数b，在b的右区间内利用"双指针"找到两个数，使这两个数之和等于target - a - b即可。

代码大体样子：两层for循环，中间套了一个双指针算法。不过这只是大体样子，还需要解决和"三数之和"同样的细节问题：结果不重且不漏。

不重："三数之和"仅有两个地方。因为这里多了一个数，所以有3个地方要保证不重

• 找到一个四元组结果，left和right都要跳过重复元素
• 每使用完一遍"双指针"，b也跳过重复元素
• b每遍历完一遍，a也跳过重复元素

不漏："双指针"找到一结果就缩小区间。

五、编写代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        // 1.排序
        sort(nums.begin(), nums.end());
        // 2.固定数a,固定数b,双指针算法
        int n = nums.size();
        for (int i = 0; i < n; )// 固定数a
        {
            // 三数之和
            for (int j = i + 1; j < n; )// 固定数b
            {
                // 双指针
                int aim = target - nums[i] - nums[j];
                int left = j + 1, right = n - 1;
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > aim) --right;
                    else if (sum < aim) ++left;
                    else
                    {
                        // 找到一结果就push_back,保证不漏缩小区间
                        ret.push_back({ nums[i], nums[j], nums[left++], nums[right--]});
                        // 去重 left和right
                        while (left < right && nums[left] == nums[left - 1]) ++left;
                        while (left < right && nums[right] == nums[right + 1]) --right;
                    }
                }
                // 去重j
                ++j;
                while (j < n && nums[j] == nums[j - 1]) ++j;
            }
            // 去重i
            ++i;
            while (i < n && nums[i] == nums[i - 1]) ++i;
        }
        return ret;
    }
};

数据范围溢出的风险，计算的时候可能会超出int的范围：

可以用long long类型的变量存储，后面的计算过程只用对第一个数据/第二个数据强制转换：

long long aim = (long long)target - nums[i] - nums[j];

long long aim = target - (long long)nums[i] - nums[j];

完整代码：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        // 1.排序
        sort(nums.begin(), nums.end());
        // 2.固定数a,固定数b,双指针算法
        int n = nums.size();
        for (int i = 0; i < n; )// 固定数a
        {
            // 三数之和
            for (int j = i + 1; j < n; )// 固定数b
            {
                // 双指针
                long long aim = target - (long long)nums[i] - nums[j];
                if (nums[i] > 0 && nums[j] > 0 && target < 0) break; 
                int left = j + 1, right = n - 1;
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > aim) --right;
                    else if (sum < aim) ++left;
                    else
                    {
                        // 找到一结果就push_back,保证不漏缩小区间
                        ret.push_back({ nums[i], nums[j], nums[left++], nums[right--]});
                        // 去重 left和right
                        while (left < right && nums[left] == nums[left - 1]) ++left;
                        while (left < right && nums[right] == nums[right + 1]) --right;
                    }
                }
                // 去重j
                ++j;
                while (j < n && nums[j] == nums[j - 1]) ++j;
            }
            // 去重i
            ++i;
            while (i < n && nums[i] == nums[i - 1]) ++i;
        }
        return ret;
    }
};

六、时间复杂度和空间复杂度

for循环嵌套for循环嵌套while循环，所以时间复杂度是O(n^3)。

空间复杂度依旧是排序算法占空间，所以空间复杂度是O(logn)。