LeetCode #15 3Sum

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #15 3Sum

문제 풀이

3개에 값을 탐색해야 하는데 n의 값이 충분히 큰 상태면 브루트포스 방식으론 해결이 안된다 시간복잡도가 $n^3$이기 때문이다. 이걸 좀 더 간소화하기 위해 포인터 기법을 써야한다. 여기선 한개의 포인터를 처음부터 오른쪽으로 진행하며 그 동안 다른 2개의 포인터가 나머지 원소들에 대해 조건이 충족되는지 검사해야 한다.

python 코드

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        sol = []
        nums.sort()
        for i in range(len(nums)):
            left, right = i + 1, len(nums) - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if s > 0:
                    right -= 1
                elif s < 0:
                    left += 1
                else: # 조건이 충족될 경우
                    sol.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 # 0이 충족된 경우 해당 케이스는 끝났으므로 다른 값으로 진행
                    right -= 1