LeetCode 15. 3Sum 16. 3Sum Closest 18. 4Sum

n數求和，固定n-2個數，最後兩個數在連續區間内一左一右根據目前求和與目标值比較移動，如果sum<target，移動較小數，否則，移動較大數

重複數處理：

使i為左至右第一個不重複數：while(i != 0 && i<n-2 && a[i] == a[i-1]) i++;

使r為右至左第一個不重複數（原序最後一個）：while(r>i && r+1<n && a[r] == a[r+1]) r--;

15. 3Sum

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        vector<int> &a = nums;
        for(int i=0; i<n-2; i++) {
            while(i != 0 && i<n-2 && a[i] == a[i-1]) i++;
            int l = i+1, r = n-1;
            while(l < r) {
                int s = a[i]+a[r]+a[l];
                if(s == 0) {
                    ans.push_back({a[i], a[l], a[r]});
                    l++; r = n-1;
                    while(l<r && a[l] == a[l-1]) l++;
                } else if(s < 0) {
                    l++;
                    while(l<r && a[l] == a[l-1]) l++;
                } else {
                    r--;
                    while(r>i && r+1<n && a[r] == a[r+1]) r--;
                }
            }
        }
        return ans;
    }
};      

16. 3Sum Closest

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int mind = INT_MAX, ans = 0;
        vector<int> &a = nums;
        for(int i=0; i<n-2; i++) {
            int l = i+1, r = n-1;
            while(l < r) {
                int s = a[i]+a[r]+a[l];
                int d = abs(s - target);
                if(s == target)
                    return s;
                else if(d < mind) {
                    mind = d;
                    ans = s;
                }
                if(s < target)
                    l++;
                else
                    r--;
            }
        }
        return ans;
    }
};      

18. 4Sum

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

轉載于:https://www.cnblogs.com/huwtylv/p/9398303.html