3Sum + 3SumClosest + 3SumSmaller

Vector : need skip repeat element using while, can extend to k-sum

(sort, 做 k-2 次循环， 从最内层循环左右夹逼，时间复杂度 O( max( nlog(n), n^(k-1) )

Set: if insert same element, skip automatically.

Sort, set to vector

Two pointers: 左右夹逼 ：`j= i + 1; k = n - 1; j++, or k--, or j++; k--

3Sum

Bug: repeat elements
Input: [-2,0,0,2,2]
Output: [[-2,0,2],[-2,0,2]]
Expected: [[-2,0,2]]

solution 1: set

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // bug: will insert same result
        //vector<vector<int> > res;
        set<vector<int> > res;


        int n = nums.size();
        if (n < 3) 
            return {};

        sort(nums.begin(), nums.end());

        for (int i = 0; i < n - 2; i++) {
            // !!! important tip!!!!!
            if (i == 0 || nums[i] != nums[i-1]) {

                int j = i + 1;
                int k = n - 1;
                while (j < k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == 0) {
                        //res.push_back( {nums[i], nums[j], nums[k]});
                        res.insert( {nums[i], nums[j], nums[k]});
                        j++;
                        k--;
                    } else if (sum < 0) {
                        j++;
                    } else {
                        k--;
                    }
                }

            }
        }

        for (vector<int> const &ve : res) {
        for (auto it : ve)  cout << it << ' ';

            cout << endl;
    }

        // convert set<vector<int> > to vector<vector<int> >  
        // way2: copy
        //vector<vector<int> > resv(res.size());
        //copy(res.begin(), res.end(), resv.begin());

        // way1: range constructor
        //vector<vector<int> > resv(res.begin(), res.end());

        // way3: std::vector::assign
        vector<vector<int> > resv;
        resv.assign(res.begin(), res.end());

        return resv;

    }
};

Solution 2: Vector using while skip --- k-sum

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > res;

        int n = nums.size();
        if (n < 3) return res;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < n - 1; ++i) {
            // important condition!!
            if ( i > 0 && nums[i] == nums[i-1]) continue;
            // bug: [-4, -1, -1, 0, 1, 2], will skip [-1, -1, 2]
            //if (nums[i] == nums[i+1]) continue;

            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    res.push_back( {nums[i], nums[j], nums[k]} );
                    ++j;
                    --k;
                    // first --k, then check nums[k] == nums[k+1]
                    // only increase from one side is OK
                    while (nums[j] == nums[j-1] && nums[k] == nums[k+1] && j < k) ++j;
                } else if (sum < 0) {
                    ++j;
                    while (nums[j] == nums[j-1] && j < k) ++j;
                } else {
                    --k;
                    while (nums[k] == nums[k+1] && j < k) --k;
                }
            }
        }

        return res;
    }
};

3Sum Closest

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans;
        int min_gap = INT_MAX;
        int n = nums.size();
        if (n < 3) return 0;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < n -1; ++i) {
            int j = i + 1;
            int k = n -1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k]; 
                int gap = abs(sum- target);

                if ( gap < min_gap) {
                    ans = sum;
                    min_gap = gap;
                }
                // Notice!!!
                if (sum < target) ++j;
                else --k;
            }
        }
        return ans;
    }
};

3Sum Smaller

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int ans = 0;
        int n = nums.size();
        if (n < 3) return 0;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < n -1; ++i) {
            int j = i + 1;
            int k = n -1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k]; 
                //cout << "i " << i<< " j: " << j <<" k: " << k << " sum: " << sum << endl;

                if (sum < target) {
                    // bug
                    //ans++;
                    ans += k - j;
                    ++j;
                } else 
                    --k;
            }
        }
        return ans;
    }
};