My 52ms C++ solution with explanation

  • 0
    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    int N = (int)nums.size();
    if (N < 3) return res;
    sort(nums.begin(), nums.end());
    vector<int> temp;
    int i = -1;//i is the first element of the duplicate to avoid missing results.
    while (i < N) {
        if (nums[i] > 0) break;//starting from element greater than 0 doesn't make sense.
        int low = i + 1;
        int high = N - 1;
        //two sum search
        while (low < high) {
            while (low < high && nums[high] + nums[low] > -nums[i]) high--;
            while (low < high && nums[high] + nums[low] < -nums[i]) low++;
            if (low < high && nums[high] + nums[low] == -nums[i]) {
                //deal with duplicates
                while (nums[high-1] == nums[high]) high--;
                while (nums[low+1] == nums[low]) low++;
        //deal with duplicates of nums[i] as well.
        while (nums[i+1]==nums[i]) i++;
    return res;

    This problem can be transformed to be the twoSum problem. So we can traverse each element in nums array, and find two elements which have the given sum. So we can use twoSum squeezing algorithm to solve it. However, we have to deal with duplicates, so after we find the twoSum, we have to avoid pushing same results by moving low and high. And we have to deal with duplicate num[i]

Log in to reply

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