15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

• new solution uupdate 2022.04.01

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

class Solution {
private:
    vector<int> removeThreeTimesDuplicatedDigits(vector<int>& nums) {
        int numOfDigits[200001] = {0, };
        vector<int> twoTimesDuplicatedDigits;

        twoTimesDuplicatedDigits.reserve(nums.size());

        for(int num : nums) {
            if(numOfDigits[num + 100000] < 2 || (num == 0 && numOfDigits[num + 100000] < 3)) {
                twoTimesDuplicatedDigits.push_back(num);
                numOfDigits[num + 100000]++;
                cout<<numOfDigits[num + 100000]<<endl;
            }
        }

        sort(twoTimesDuplicatedDigits.begin(), twoTimesDuplicatedDigits.end());
        return twoTimesDuplicatedDigits;
    }
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int> twoDuplicatedDigits = removeThreeTimesDuplicatedDigits(nums);

        vector<vector<int>> solution;

        for(int i = 0; i < twoDuplicatedDigits.size() && twoDuplicatedDigits[i] <= 0; i++) {
            if(i >= 1 && twoDuplicatedDigits[i] == twoDuplicatedDigits[i - 1]) continue;
            for(int j = i + 1; j < twoDuplicatedDigits.size() && twoDuplicatedDigits[i] + 2 * twoDuplicatedDigits[j] <= 0; j++) {
                if(j - 1 != i && twoDuplicatedDigits[j] == twoDuplicatedDigits[j - 1]) continue;
                if(binary_search(twoDuplicatedDigits.begin() + j + 1, twoDuplicatedDigits.end(), -(twoDuplicatedDigits[i] + twoDuplicatedDigits[j])))
                    solution.push_back(vector<int>{twoDuplicatedDigits[i], twoDuplicatedDigits[j], -(twoDuplicatedDigits[i] + twoDuplicatedDigits[j])});
            }
        }

        return solution;
    }
};