【算法专题突破】双指针 - 四数之和（8）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法专题突破】双指针 - 四数之和（8）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

1. 题目解析

题目链接：18. 四数之和 - 力扣（Leetcode）

【算法专题突破】双指针 - 四数之和（8）,算法专题训练,leetcode,算法,c++,学习

这道题跟三数之和也是一样的，

题目很好理解，就是四个数的和等于target的情况，

且这四个数不能重复。

2. 算法原理

首先还是暴力解法：

排序 + 暴力枚举 + set去重

我们当然是用优化的解法：

1. 依次固定一个数a

2. 然后在后面的区间，找到他们的和为target - a的数

3. 而三数之和，也是固定一个数b，然后找出他们的和为target - a - b的数

但是我们也要注意，需要跳过重复元素。

3. 代码编写

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, long long target) {
        int size = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < size - 3; i++) {
            int a = nums[i];
            for(int j = i + 1; j < size - 2; j++) {
                int b = nums[j];
                int left = j + 1, right = size - 1;
                while(left < right) {
                    int sum = nums[left] + nums[right];
                    if(sum < target - a - b) left++;
                    else if(sum > target - a - b) right--;
                    else { // sum == target - a - b
                        ans.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--;
                        left++, right--;
                    }
                }
                while(j < size - 2 && nums[j] == nums[j + 1]) j++;
            }
            while(i < size - 3 && nums[i] == nums[i + 1]) i++;
        }
        return ans;
    }
};