[Reet code] 3Sum

Intuition

한 점을 고정한 후 투포인터로 풀 수 있다.

Approach

처음에는 두 숫자의 합에 나머지 숫자로 하려고, 전에 풀었던 다른 문제와 비슷하게 접근했다. 숫자를 객체로 만들어서, a + b = 0 이 되게 하게끔 a = -b 인 값을 찾는 방식으로 했다. 그런데 중복 제거하는데 시간이 너무 소요되서 결국 다른 사람 코드를 봤다.

방법은 간단하다. 한점을 고정한 후에 투포인터를 쓰면서 0보다 크면 right bound 를 줄이고, 0보다 작으면 left bound 를 올린다. 물론 정렬된 상태여야 한다.

Complexity

• Time complexity: O(NlogN)
  sort 를 해서 O(NlogN) 의 시간복잡도를 가진다. 반복문 안에 반복문이 있긴 하지만 정렬과 동일하거나 더 작은 복잡도를 가진다.

• Space complexity: O(1)

Code

function threeSum(nums) {
	const results = []
    if (nums.length < 3) return results

	nums = nums.sort((a, b) => a - b)

	let target = 0

	for (let i = 0; i < nums.length - 2; i++) {
		if (nums[i] > target) break // 모두 양수
		if (i > 0 && nums[i] === nums[i - 1]) continue

		let j = i + 1 // ->
		let k = nums.length - 1 // <-
		
		while (j < k) {
			let sum = nums[i] + nums[j] + nums[k]

			if (sum === target) {
				results.push([nums[i], nums[j], nums[k]])

				while (nums[j] === nums[j + 1]) j++
				while (nums[k] === nums[k - 1]) k--

				j++
				k--

			} else if (sum < target) {
				j++

			} else { // (sum > target)
				k--
			}
		}
	}

	return results
};