[LeetCode] 15. 3Sum

1. 문제

https://leetcode.com/problems/3sum

3Sum - LeetCode

2. 접근 방법

단순히 for문을 3개 쓰면 O(n3)로 해결할 수 있ㄱㅆ지만

투포인터를 사용하면 O(n2)로 해결할 수 있습니다 !!!!!!!!!

 

1. 주어진 숫자들을 오름차순 정렬한다.

2. 반복문 하나와 투포인터를 사용해서 각각의 경우의 합을 구하고 만약 해당 idx에서의 value값과 left value, right value합이 0보다 클 경우 오른쪽 포인터 위치를 왼쪽으로 한 칸 옮기고, 0보다 작을 경우 왼쪽 포인터 위치를 오른쪽으로 한 칸 옮긴다.

3. 만약 합이 0인 경우 results에 담아주고 반복문에서 다음idx로 넘어간다.

3. 코드

python3

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()
        
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            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:
                    results.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 results

4. 마치며

참고로 저 코드 실행하려면 `from typing import List` 해줘야해용