runtime 12 ms, beats 98.62% of cpp submissions
O(n^3) solution with explanation

tags: two pointer, recursion

4sum

📖 description

給定一個未排序的陣列 nums ，與要尋找的目標 target ，在 nums 中找出所有 不重複 的組合 (4 個數字)，滿足數值總和 target 。

🧠 solution

在 4sum 題目中，其實無論要挑幾個數字，他們的過程都是相似的，所以這邊就直接解決最大的問題 ksum 。

首先，與 two sum 的做法類似，必須先將陣列 sort 過一次，這樣之後在做雙指標時才會得到正確的結果。

無論 k 是多少，其實我們只需要想一個情況，對於 k=3 ，我們可以先固定一個起始點，然後針對該點後方的元素找 two sum ( target-nums[i] )，接著再組合前面的固定點，問題就解決了。而當問題擴展到 4sum ，我們其實也只要找到一個固定點，接著對該點後方的元素找 3sum 。

⏳ time complexity

如果 k=2 ，時間主要花在 sort ，時間複雜度 O(nlog(n)) (雙指標時間複雜度 O(n) )
如果 k>=3 ，時間主要花在決定固定點並對後方搜尋，時間複雜度 O(n^(k-1))
總時間複雜度 O(n^3)

📝 code

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
class Solution {
public:
    vector<vector<int>> two_sum(vector<int>& nums,int start,long t){
        vector<vector<int>> ans;
        int l = start,r = nums.size()-1;
        while(r>l){
            // 為了避免重複挑選，需要避開相等項
            if(nums[l]+nums[r]>t || (r<nums.size()-1 && nums[r]==nums[r+1])){
                r--;
            }
            // 為了避免重複挑選，需要避開相等項
            else if(nums[l]+nums[r]<t || (l>start && nums[l]==nums[l-1])){
                l++;
            }
            else{
                ans.emplace_back(vector<int>{nums[l],nums[r]});
                l++;
                r--;
            }
        }
        return ans;
    }
    vector<vector<int>> k_sum(vector<int>& nums,int start,int k,long t){
        vector<vector<int>> ans;

        // 加速，如果陣列頭的 k 倍已經超過 target ，或是陣列尾的 k 倍小於 target ，表是一定不會符合
        if(start==nums.size() || (long)nums[start]*k>t || (long)nums.back()*k<t) return ans;

        // 終止條件，當 k=2 直接回傳 two sum
        if(k==2){
            return two_sum(nums,start,t);
        }
        for(int i=start;i<nums.size();i++){                // 決定固定點
            // 為了避免重複挑選，需要避開相等項
            if(i==start || nums[i-1]!=nums[i]){
                auto karr = k_sum(nums,i+1,k-1,t-nums[i]); // 拿故定點後方的元素做 (k-1) sum
                for(int j=0;j<karr.size();j++){

                    //建構答案
                    ans.emplace_back(vector<int>{nums[i]});
                    ans.back().insert(ans.back().end(), karr[j].begin(),karr[j].end());
                }
            }
        }
        return ans;
    }
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end()); // 確保 two sum 正確
        return k_sum(nums,0,4,target);
    }
};