LeetCode - 15. 3Sum

Thoughts:

In Two Sum, I can just focus on handle the diff as key and the index as value with hash map. But !!!! In 3Sum problem, It’s totally different. First, it’s O(n³) if I choose the brute-force way. So the goal is to reduce the complexity to O(n²). The description says that the order is not matter, so I can do sorting (the complexity is O(nlogn)) the array first. Then, I can use two-pointer inside a loop to solve this problem (the complexity will be O(n²)). In the end, it’s like O(n²+nlogn) => O(n²).

Thoughts visuzlization:

for example

nums = [-1,0,1,2,-1,-4]

and make the sum of three nums is 0

sort the array

[-1,0,1,2,-1,-4] -> [-4,-1,-1,0,1,2]

loop through the array, and use two-pointer inside the loop

set i as the current index of loop, l as the left pointer, and r as the right pointer

and keep narrowing the range of l and r to find the sum of three nums is 0

[-4,-1,-1,0,1,2]
  i  l        r

-4 + -1 + 2 = -3, and -3 < 0, sum is too small, so move l to next index

[-4,-1,-1,0,1,2]
  i     l     r

-4 + -1 + 1 = -4, and -4 < 0, sum is too small, so move l to next index

keep doing this when l < r, until l is not small than r anymore, i + 1

[-4,-1,-1,0,1,2]
     i  l     r

-1 + -1 + 2 = 0, and 0 === 0, push the result to the answer array

when found sum is 0, move l to next index and r to previous index

doing this because the array is sorted, and i is fixed in this one loop iteration

if just move l or r, maybe will get the same num and make the same sum again

if l or r keep finding the same num, then l or r needd to keep moving forward or backward

do those things to avoid the duplicate answer

[-4,-1,-1,0,1,2]
     i    l r

the sum is 0, so do the same things like above

[-4,-1,-1,0,1,2]
     i    r l

l is not smaller than r anymore, i + 1

[-4,-1,-1,0,1,2]
        i l r

if nums[i] === nums[i - 1], then need to skip this one loop iteration

because the array is sorted, so the previous same num has already found all the possible result

[-4,-1,-1,0,1,2]
        i l r

[-4,-1,-1,0,1,2]
          i l r

0 + 1 + 2 = 3, and 3 > 0, sum is too big, so move r to previous index

[-4,-1,-1,0,1,2]
          i l
            r

l is not small than r anymore, i + 1

[-4,-1,-1,0,1,2]
            i l r

i is not qualified, because no room for r, so this loop is done

Code:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const answer = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum === 0) {
        answer.push([nums[i], nums[l], nums[r]]);
        while (nums[l] === nums[l + 1]) {
          l++;
        }
        while (nums[r] === nums[r - 1]) {
          r--;
        }
        l++;
        r--;
      } else if (sum < 0) {
        l++;
      } else {
        r--;
      }
    }
  }
  return answer;
};

Reference

Original link

What is Array.prototype.sort() time complexity?

The Two Pointers Technique in JavaScript