[LeetCode] 15. 3Sum

 Given an integer array nums, return all the triplets [nums[i], nums[j]. nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

 Notice that the solution set must not contain duplicate triplets.

---

• 가장 먼저 떠올린 방법은 주어진 수열을 3중 for문을 이용하여 $O(n^3)$의 시간복잡도를 가지도록 코딩하는 것이었다.

• 시간복잡도가 굉장히 커지는 만큼 Timeout이 될 거라고 예상하였지만, 일단 작성해보았다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[int]:
        triplets = []
        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]: continue
            for j in range(i + 1, len(nums) - 1):
                if j > i + 1 and nums[j] == nums[j - 1]: continue
                for k in range(j + 1, len(nums)):
                    if k > j + 1 and nums[k] == nums[k - 1]: continue
                    if nums[i] + nums[j] + nums[k] == 0:
                        triplets.append([nums[i], nums[j], nums[k]])

        return triplets

• 위 테스트케이스처럼 매우 긴 수열이 들어올 경우 시간초과가 되는 것을 확인할 수 있었다.

---

• 리트코트에서 제공하는 힌트를 확인해보니, 숫자 하나를 고정한 후 나머지 두 수에 대해 2Sum 방식을 활용하라고 적혀있어서 두 수를 더해 원하는 숫자가 나오는 숫자쌍을 빠르게 구하는 방법을 찾아보았다.
  • 수열을 순회하며 하나의 수를 정하고, target에서 그 수를 뺀 값을 in조건을 사용하여 찾는다. in의 시간복잡도는 $O(n)$으로 동일하지만, 파이썬에서는 for문을 통해 수열을 순회하는 것보다 in연산을 사용하는 것이 훨씬 빠르다.
  • 수열을 sort()한 뒤, 양 끝에 포인터를 두고 두 수의 합이 target보다 클 경우 오른쪽에 있는 포인터를 한 칸 앞으로, target보다 작을 경우 왼쪽에 있는 포인터를 한 칸 뒤로 미는 연산을 반복한다. target을 구하거나 두 포인터가 교차할 때 까지 진행되므로 시간복잡도는 $O(n)$이다.
• 아래의 방법이 조금 더 직관적이고 실행되는 연산의 갯수도 적다고 생각되어 아래의 방법을 채택하였다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[int]:
        def twoSum(nums_sub: List[int], target: int) -> List[List[int]]:
            left = 0
            right = len(nums_sub) - 1
            res = []
            while left < right:
                if nums_sub[left] + nums_sub[right] > target:
                    right -= 1
                elif nums_sub[left] + nums_sub[right] < target:
                    left += 1
                else:
                    triplet = [0 - target, nums_sub[left], nums_sub[right]]
                    if triplet not in res:
                        res.append([0 - target, nums_sub[left], nums_sub[right]])
                    right -= 1
                    left += 1
            return res

        res = []
        nums.sort()
        for i, n in enumerate(nums[:-2]):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            target = 0 - n
            twosum_res = twoSum(nums[i + 1:], target)
            if twosum_res:
                res.extend(twosum_res)

        return res

• 적절한 시간 안에 답을 구하는 것을 확인할 수 있었다.