題目： LeetCode - 18. 4Sum

解題思路

基本上和 LeetCode - 15 解題紀錄 的想法相同，只是要固定的點從一個變兩個，11 行和 12 行的兩個判斷是為了使執行速度更快，由於陣列是排序過的，所以 11 行的條件成立表後面的 nums[i] 都不可能符合條件，若 12 行的條件成立表 nums[i] 太小，直接往後做即可。

參考解法

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