[LeetCode Road] 3Sum - Solution/C++

15. 3Sum

Question:

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.

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: nums = []
Output: []

Input: nums = [0]
Output: []

Constraints:

0 <= nums.length <= 3000

-10⁵ <= nums[i] <= 10⁵

Source code:

Version 1

Idea:
The input is unsorted data, it's hart to find a rules to solve it. Therefore, sort nums first.

There are some situations that the program doesn't run necessarily, the explanation of situations are shown as below:
1) The sum of the first three elements is bigger than 0, it means any elements is bigger than 0, so directly break the loop at 11 line.
2) If add the first element nums[i] to the last element nums[n-1] and the second to last element nums[n-2] is small than 0, it's represnets whatever the calculation of sum is always negative number, so directly move i to the next index at 13 line.
3) Avoid the duplicate elements and results at 15 line, because all the possibility are found at nums[i-1].

Then, declare two variables to point the i+1 position and the tail of arrayv n-1. There is a search range between i+1 and n-1.

If nums[i] + nums[j] + nums[k] is not equal to 0, move j to the next index when the sum is small than 0 or move k to previous index when the sum is bigger than 0.

If nums[i] + nums[j] + nums[k] is equal to 0, push these elements to 2D vector first, then narrow the search range down, must to check whether the next element is the same as the previous one for avoid the duplicate result at 22 - 27 line.

Time complexity: O(nlogn + n²)
Space complexity: O(1)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        const int n  = nums.size();
        vector<vector<int>> res;
        //if(n < 3) return res;
        
        sort(nums.begin(), nums.end());
        
        for(int i = 0; i < n - 2; i++){
            if(nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
            /*the beginning element is bigger than 0, directly break the loop*/
            if(nums[i] + nums[n - 1] + nums[n - 2] < 0) continue;
            /*the beginning element add to the most largest element and the element largest element you get result, if result is negative, no reason to calculate*/
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            /*ensure the results are not contain duplicat triplets
            'i > 0' statement is necessary for input:[0,0,0]*/
            int j = i + 1;
            int k = n - 1;
            while(j < k){
                //cout << nums[i] << " " << nums[j] << " " <<nums[k] << endl;
                int tmp = nums[i] + nums[j] + nums[k];
                if(tmp == 0){
                    res.push_back({nums[i] , nums[j] , nums[k]});
                    ++j;
                    while(j < k && nums[j] == nums[j - 1]) ++j;
                    --k;
                    while(j < k && nums[k] == nums[k + 1]) --k;
                }else if(tmp < 0){
                    ++j;
                }else if(tmp > 0){
                    --k;
                }
            }
        }
        return res;
    }
};
};