LeetCode/fourSum.cpp at main · zxk-creator/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        //set自动去重
        set<vector<int>> resultArr;
        sort(nums.begin(),nums.end());
        int n = nums.size() - 3;
        for (int i = 0; i < n - 3; i++)
        {
            //跳过重复元素，以及检测四个连续的数的和是否大于了target，如果是，那么直接返回
            if((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            //如果当前数加上最大数还小于Target，那么索性直接跳过
            if((long long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
            for(int j = i + 1;j < n - 2;j++)
            {
                // 跳过重复元素，以及检测四个连续的数的和是否大于了target，如果是，那么直接返回
                if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
                    break;
                // 如果当前数加上最大数还小于Target，那么索性直接跳过
                if ((long long)nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target)
                    continue;
                //固定住两个数后，使用双指针遍历剩余的两个数
                int left = j + 1;
                int right = n - 1;
                while(left < right)
                {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target)
                    {
                        resultArr.insert({nums[i],nums[j],nums[left],nums[right]});
                    }
                    if(sum < target)
                    {
                        left++;
                    }
                    else
                    {
                        right--;
                    }
                }
            }
        }

        return vector<vector<int>>(resultArr.begin(),resultArr.end());
    }
};