力扣(LeetCode)18. 四数之和(C++)

双指针

快排使 $nums$ 正序。

设置四个指针 $i$ 指向 $nums$ 第一个数，$j$ 指向 $nums$ 第二个数，从前往后枚举 $nums[i]$ 和 $nums[j]$ ， $l$ 从 $nums[j+1]$ 往后，指向第三个数，$r$ 从 $nums.size()-1$ 往左，指向第四个数。

设四数之和 $nums[i]+nums[j]+nums[l]+nums[r]=sum$ ，如果 $sum>target$ ，为了接近 $target$ ， $r--$ 。 同理， $sum<target$ ， 为了接近 $target$ ， $l++$ 。

如果 $sum=target$ 得到一个答案，为了避免重复答案， $l$ 循环右移，直到遇到不重复元素，同理 $r$ 循环左移 。

代码展示

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> ans;
        if(nums.size()<4) return ans;
        sort(nums.begin(),nums.end());
        for(int i = 0;i<n-3;i++){
            if(i&&nums[i]==nums[i-1]) continue;
            for(int j = i+1;j<n-2;j++){
                if(j!=i+1&&nums[j]==nums[j-1]) continue;
                int l = j+1,r = n - 1;
                while(l<r){
                    long long sum = (long long)nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum>target) r--;
                    else if(sum<target) l++;
                    else{
                        ans.push_back({nums[i],nums[j],nums[l],nums[r]});
                        while(l<r&&nums[l]==nums[l+1]) l++;
                        while(l<r&&nums[r]==nums[r-1]) r--;
                        l++;
                        r--;
                    }
                }
            }
        }
        return ans;
    }
};
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

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(n^3)$， $n$ 是 $nums$ 的长度 ， 枚举 $nums[i]$ 和 $nums[j]$ ，同时双指针枚举 $nums[l]/nums[r]$ 的时间复杂度 $O(n^3)$ 。
2. 空间复杂度: $O(logn)$，快排的平均空间复杂度 $O(logn)$ 。