한 점을 고정한 후 투포인터로 풀 수 있다.
처음에는 두 숫자의 합에 나머지 숫자로 하려고, 전에 풀었던 다른 문제와 비슷하게 접근했다. 숫자를 객체로 만들어서, a + b = 0 이 되게 하게끔 a = -b 인 값을 찾는 방식으로 했다. 그런데 중복 제거하는데 시간이 너무 소요되서 결국 다른 사람 코드를 봤다.
방법은 간단하다. 한점을 고정한 후에 투포인터를 쓰면서 0보다 크면 right bound 를 줄이고, 0보다 작으면 left bound 를 올린다. 물론 정렬된 상태여야 한다.
Time complexity: O(NlogN)
sort 를 해서 O(NlogN) 의 시간복잡도를 가진다. 반복문 안에 반복문이 있긴 하지만 정렬과 동일하거나 더 작은 복잡도를 가진다.
Space complexity: O(1)
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
};