15. 3Sum

하나의 array가 주어질 때 triplets(세 쌍둥이)의 합을 구하되, 0이 되도록 하는 경우들을 list에 넣어서 출력해야 한다. 입력으로 주어진 배열의 모든 요소를 순회하면서 세 개의 요소의 합이 0이 되는 경우를 찾는 것이다. 따라서 입력 배열의 크기가 커질수록 시간 복잡도는 증가하게 된다. 밑에 첫 번째 시도에서 시간 복잡도에 발목이 붙잡혔다.

first attempt

처음엔 그냥 brute force 방식으로 해보려고 했다. 하지만 이러한 방식은 time limit excess에러가 났다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        hash = {}
        size = len(nums)

        # all other cases with hash table
        for i in range(size):
            for j in range(i+1,size):
                for k in range(j+1,size):
                    this = str(nums[i] + nums[j] + nums[k])
                    elem = sorted([nums[i],nums[j],nums[k]])
                    if this in hash:
                        if elem in hash[this]:
                            continue
                        hash[this].append(elem)
                    else:
                        hash[this] = [elem]
        if '0' in hash.keys():
            return hash['0']
        else:
            return []

이런 방식으로 하면 for문을 3번 돌기 때문에 O(n^3)의 시간 복잡도를 가지게 된다. hash map을 사용하려고 했고, 결과를 저장해야 한다는 개념은 있었으나 좀 더 시간 복잡도를 줄이기 위한 노력이 필요했다.

second attempt(sol)

시간복잡도는 다음과 같다.
1. 배열 정렬 : O(n logn)
2. main loop : O(n)
3. Two pointer loop : O(n)

O(n logn) + O(n) * O(n) 임으로 O(n^2)의 시간복잡도를 가진다.

def threeSum(nums):
    nums.sort()  # 배열 정렬
    result = []

    for i in range(len(nums)):
        # 중복된 값 건너뛰기
        if i > 0 and nums[i] == nums[i-1]:
            continue

        # Two Pointers 초기화
        left, right = i + 1, len(nums) - 1
        while left < right:
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0:
                left += 1
            elif sum > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                # 중복된 값 건너뛰기
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1

    return result

배열을 정렬해서 오름차순으로 만들어준다. 이를 통해서 뒤에서 two pointer를 활용할 수 있게 된다. 이후에 고정된 포인트와 두 포인터를 사용한다. 배열의 각 요소에 대해, 해당 요소를 고정한 후 나머지 배열에 대해 두 포인터를 사용해서 0이 되는 쌍을 찾는다. 이후에 같은 요소를 중복으로 사용하지 않도록 한다.

hash_table

two pointer 말고 맨 처음에 생각했던 것은 hash를 이용하는 방법이라서 이에 대해서도 코드를 남겨놔야겠다.

def 3Sum(nums):
  nums.sort()
  result, duplicate = set(),set()
  seen = ()

  for i,val1 in enumerate(nums):
    if val1 not in duplicate:
      duplicate.add(val1)
      for val2 in nums[i+1:]:
        complement -= -val1 + val2
        if complement in seen and seen[complement] == i:
          result.add((val1,val2, complement))
        seen[val2] = i

  return list(result)

중복을 다루기 위해서 순서에 상관없는 set를 이용해준다. 두 숫자의 합을 찾을 때, 배열의 각 요소에 대해, 나머지 배열에서 두 숫자의 합이 현재 숫자의 반대(-)값과 일치하는 쌍을 찾는다.

해시 테이블(seen)은 각 숫자의 마지막 인덱스를 저장한다. complement가 이미 seen에 있는지를 확인하고, 그 complement 값이 현재 숫자 val1의 인덱스와 동일한지(complement가 val1과 동일한 숫자가 아니며, 현재 숫자 조합에 적합한지)를 확인한다.