15. 3Sum (Array, Two Pointers, Sorting)

링크 - https://leetcode.com/problems/3sum/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-three-months

난이도 - Medium

Intuition

우리는 TwoSum문제를 푼 방식과 같은 방법으로 문제를 풀 수 있다.

1. nums를 sort한다. 그다음 nums를 for문으로 돌리면서 num이 0보다 크면 앞의 수들은 다 더해도 0보다 크게 되므로 break를 건다.

2. 만약 i == 0 이거나 nums[i-1] != nums[i]이면 TwoSum을 한다.

3. j = i+1부터 시작하여 하나씩 올려간다. 만약 -nums[i] - nums[j]가 target에 있다면 ans에 답으로 집어넣는다. 그리고 nums[j]가 다른 값이 나올때까지 계속 올린다.

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []

        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i == 0 or nums[i-1] != nums[i]:
                self.twoSum(nums, i, ans)

        return ans

    def twoSum(self, nums, i, ans):
        visited = set()
        j = i + 1
        while j < len(nums):
            target = -nums[i] - nums[j]
            if target in visited:
                ans.append([nums[i], nums[j], target])
                while j + 1 < len(nums) and nums[j] == nums[j+1]:
                    j += 1
            visited.add(nums[j])
            j += 1

Complexity

Time Complexity: O(N^2)

Space Complexity: O(N)