四数之和 - 力扣中等

题目链接

四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：
$$\begin{gathered} 1<=nums.length<=200 \\ -10^9<=nums[i]<=10^9 \\ -10^9<=target<=10^9 \end{gathered}$$

解题思路

思路一

双指针，时间复杂度为$O(N^3)$
排序
枚举前两个数字，剩下两个使用双指针l和r枚举。

• 如果nums[l] + nums[r] == target - nums[i] - nums[j]，找到答案，更新l和r。
• 如果nums[l] + nums[r] > target - nums[i] - nums[j]，找到答案，r左移。
• 如果nums[l] + nums[r] < target - nums[i] - nums[j]，找到答案，l右移。

思路二

二分查找，时间复杂度为$O(N^{3}logN)$
排序
枚举前三个数字，查找第四个数target - nums[i] - nums[j] - nums[k]是否在数组里面。
很不幸，跑到最后一个测试用例超时。

注意溢出！

解题代码

思路一

#include
#include
#include
#include
using namespace std;

class Solution {

public:
    vector<vector<int>>ans;
    map<int,map<int,map<int,bool>>>vis;

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                int l=j+1;
                int r=nums.size()-1;
                long long tmp_target = (long long)target-nums[i]-nums[j];

                while(l<r){
                    if(l==i||l==j){
                        l++;
                        continue;
                    }
                    if(r==i||r==j){
                        r--;
                        continue;
                    }
                    long long lr_sum = (long long)nums[l]+nums[r];
                    if(lr_sum==tmp_target){
                        if(vis[nums[i]][nums[j]][nums[l]]==0){
                            vis[nums[i]][nums[j]][nums[l]]=1;
                            vector<int>path = {nums[i],nums[j],nums[l],nums[r]};
                            ans.push_back(path);
                        }

                        l++;
                        r--;
                        continue;
                    }
                    if(lr_sum<tmp_target){
                        l++;
                        continue;
                    }
                    if(lr_sum>tmp_target){
                        r--;
                        continue;
                    }
                }


            }
        }

//        for(int i=0;i
//            vectorpath=ans[i];
//            for(int p=0;p
//                cout<
//            }cout<
//        }
        return ans;
    }
};

int main(){
    //-2，-1，0，0，1，2
    vector<int>nums = {0,0,0,0};
    int target = 1;
    Solution so = Solution();
    so.fourSum(nums,target);

    return 0;
}

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

思路二 (超时)

最后一个测试用例超时

#include
#include
#include
#include
using namespace std;

class Solution {
public:
    vector<vector<int>>ans;
    map<int,map<int,map<int,bool>>>vis;
    int binary_search(vector<int>&nums, int sidx, int target){
        int l=sidx;
        int r=nums.size()-1;
        while(l<r){
            int m = (l+r)>>1;
            if(nums[m]==target)return m;
            if(nums[m]<target)l=m+1;
            else r=m-1;
        }
        if(l<nums.size()&&nums[l]==target)return l;
        return -1;
    }
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                for(int k=j+1;k<nums.size()-1;k++){
                    if(vis[nums[i]][nums[j]][nums[k]])continue;
                    long long d = (long long)target-nums[i]-nums[j]-nums[k];
                    if(d<nums[k+1]||d>nums[nums.size()-1])continue;
                    int idx = binary_search(nums,k+1,d);
                    if(idx!=-1){
                        vis[nums[i]][nums[j]][nums[k]]=1;
                        // vectorpath = {nums[i],nums[j],nums[k],nums[idx]};
                        ans.push_back({nums[i],nums[j],nums[k],nums[idx]});
//                        for(int p=0;p
//                            cout<
//                        }cout<
                    }
                }
            }
        }
        return ans;
    }
};

int main(){
    //-2，-1，0，0，1，2
    vector<int>nums = {0,0,0,0};
    int target = 1;
    Solution so = Solution();
    so.fourSum(nums,target);

    return 0;
}

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
56