18. 4Sum

1.問題

2.想法

• 提問

• function header, parameter

• test input

• 說明想法

  • 對序列後排序

  • 跟3 sum的做法很像, 但使用3個迴圈

  • 由於edge case會出現類似(0, 0 ,0, 0), 因此不能像3 sum一樣跳過重複的字母

    • 用set來記錄vector, 最後再將set轉為vector

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

• 分別使用4個指標, 依題意的目的是要總和為target

  • 若總和 == 0, 則記錄i, j , k, l的數值

  • 若總和 < 0, 則表示總和太小, 讓k++

  • 若總和 > 0, 則表示總和太大, 讓l--

• 測試計算複雜度: O(n^3) ?

3.程式碼

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int size = nums.size();
        set<vector<int>> res;
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < size - 3; i++) {
            for (int j = i + 1; j < size - 2; j++) {
                int k = j + 1;
                int l = size - 1;
                while (k < l) {
                    int sum = nums[i] + nums[j] + nums[k] + nums[l];
                    if (sum == target) {
                        res.insert({nums[i], nums[j], nums[k], nums[l]});
                        k++;
                        l--;
                    } else if (sum < target) {
                        k++;
                    } else {
                        l--;
                    }
                }
            }    
        }
            
        return vector<vector<int>>(res.begin(), res.end());
    }
};