15. 3Sum

1. brute force

시간 초과나옴.

class Solution:
    def threeSum(self, nums):
        nums.sort()
        results = []

        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:
                        results.append([nums[i], nums[j], nums[k]])
        
        return results

2. 포인터 이동

class Solution2:
    def threeSum(self, nums):
        nums.sort()
        results = []

        for i in range(len(nums) - 2):
            # 같은 조합 걸러줘야함
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left = i + 1
            right = len(nums) - 1

            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum == 0:
                    results.append([nums[i], nums[left], nums[right]])

                    # 찾았을때 left, right 값도 중복 안되게 이동 시켜줘야함
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    # left, right 값을 중복의 마지막까지 끌고왔으니 여기서 한 번 더 이동시켜줘야 중복아님.
                    left += 1
                    right -= 1
                elif sum > 0:
                    right -= 1
                else:
                    left += 1

        return results