15. 3Sum

https://leetcode.com/problems/3sum

Python

Three Pointers

大概就是Two Pointer的Two Pointer，先排序過再用三個指標走訪

• L: 左界
• M: 從L+1移動到R-1
• R: 右界，範圍內的最大值

排序過，所以可以利用當下的total大於小於0的關係，決定要移動哪一個pointer (m or r)

Origin Version which prevent duplicate via set(tuple)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []

        nums.sort()
        result = set()

        for l in range(0, len(nums)-2):
            m = l + 1
            r = len(nums)-1

            while m < r:
                total = sum([nums[l], nums[m], nums[r]])

                if total == 0:
                    result.add((nums[l], nums[m], nums[r]))
                    # Move m, r at the same time is ok, because the l has its own loop
                    m += 1
                    r -= 1
                elif total < 0:
                    # Total too small, increase it from increment the cur (the m)
                    m += 1
                else:
                    # Total too large, reduce it from decreasing the upbound
                    r -= 1

        return list(result)

Skip duplicate values with result in array

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []

        nums.sort()
        result = []

        for l in range(0, len(nums)-2):
            if l > 0 and nums[l] == nums[l-1]:
                continue

            m = l + 1
            r = len(nums)-1

            while m < r:
                if m > l+1 and nums[m] == nums[m-1]:
                    m += 1
                    continue

                total = sum([nums[l], nums[m], nums[r]])

                if total == 0:
                    result.append([nums[l], nums[m], nums[r]])
                    m += 1
                    r -= 1
                elif total < 0:
                    m += 1
                else:
                    r -= 1

        return result

Brute Force (Timelimit Exceed)

from itertools import combinations


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []

        combs = set()
        for comb in combinations(nums, r=3):
            combs.add(tuple(sorted(comb)))


        return [comb for comb in combs if sum(comb) == 0]

Prefix Sum

• No-Sort solution
• Idea of seen hashmap is pre-calcualted memory, which like prefix-sum

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []

        result = set()
        duplicates = set() # Prevent edge case, e.g. 3000 zerons
        seen = dict()  # key: remains to 0; value: index

        for i, first in enumerate(nums):
            if first in duplicates:
                continue

            duplicates.add(first)
            for j, second in enumerate(nums[i+1:]):
                remains = 0 - (first + second)
                if seen.get(remains) == i:
                    result.add(tuple(sorted([first, second, remains])))
                seen[second] = i
        return result

Javascript

var threeSum = function(nums = []) {
  const sortedNums = [...nums].sort((a, b) => a - b);
  let result = []

  for (let i = 0; i < sortedNums.length; i++) {
    if (sortedNums[i - 1] !== sortedNums[i]) {
      const target = sortedNums[i];
      console.log(target, i+ 1, sortedNums.length - 1)
      const res = calc(-target, i + 1, sortedNums.length - 1, sortedNums);
      if (res.length) result = result.concat(res);
    }
	}
  return result;
};

const calc = (target, left, right, nums) => {
  const res = [];

	while (left < right) {
		if (target === nums[left] + nums[right]) {
			res.push([-target, nums[left++], nums[right--]]);
      while(left < right && nums[left - 1] === nums[left]) {
        left++;
      }
		} else if (target > nums[left] + nums[right]) {
			left++;
		} else {
			right--;
		}
	}

	return res;
}