My C++ solution


  • 0
    I
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        for (int i = 0, bound = nums.size() - 2; i < bound && nums[i] <= 0; i++) {
    	    if (i != 0 && nums[i] == nums[i - 1]) continue;
    	    int left = i + 1, right = nums.size() - 1;
    	    while (left < right) {
    		    int sum = nums[i] + nums[left] + nums[right];
    		    if (sum > 0) {
    			    right--;
    		    } else {
    			    if (sum == 0 && (ret.empty() || nums[i] != (ret.back())[0] || nums[left] != (ret.back())[1])) {
    				    ret.push_back(vector<int>({ nums[i], nums[left], nums[right] }));
    			    }
    			    left++;
    		    }
    	    }
        }
        return ret;
    }

  • 0
    L

    @Irving_cl your solution will contain duplicates since there are more than one occurrence of a no. and you should set the indices such that similar numbers where sum == 0 do not occur again.
    For eg. [-1, 0, 1, 2, -1, -4] => [-4,-1,-1,0,1,2]
    for i=1,your solution will get first triplet at indices: (1,2,5) => [-1,-1,2] now left++, so next triplet will be (1,2,3)=> [-1,0,1]
    in next iteration for i=2 again nums[i]=-1, and triplet (2,3,4)=>[-1,0,1] get generated which is wrong.

    sol: increase i, left so that their values are not same as previous , and decrease right so that its value is not same as its previous value.


  • 0
    I

    @liveIt Thank you for pointing it out, I really appreciate it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.