3Sum

반응형

문제 링크 : leetcode.com/problems/3sum/submissions/

3Sum - LeetCode

제공되는 배열의 수 중 3개를 골라 0이 되는 수의 조합을 return 한다.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(0, len(nums) - 2):
            left = i + 1
            right = len(nums) - 1
            while left < right:
                sum = nums[i] + nums[left] + nums[right]
                if sum == 0:
                    if not [nums[i], nums[left], nums[right]] in result: 
                        result.append([nums[i], nums[left], nums[right]])
                    left += 1
                elif sum < 0:
                    left += 1
                else:
                    right -= 1
        return result

투 포인터를 이용하는 방법으로 풀었다. 이 투 포인터를 이용하는 방법 굉장히 유용하다. 순차적인 1차원 배열에서 순환하며 무언가를 얻어내야 할 때 굉장히 좋다.

일단, 투 포인터를 쓰기 위해 정렬을 해서 순차적으로 만든다. 첫번째 수는 for문을 그대로 따라가고 포인터 하나는 첫번째 수의 오른쪽부터 끝방향으로, 포인터 두번째는 끝에서 첫번째 수 방향으로 이동한다. 세 수를 더해서 작으면 첫번째 포인터를 오른쪽으로 이동 크면 두번째 포인터를 왼쪽으로 이동시켜서 만날때까지 반복한다.

여기까지가 내가 이해한 내용.

책 보니깐 중복된 값 스킵하는 것과 포인터들을 이동시킬때 값이 같으면 스킵하고 또 이동시키는 부분이 빠졌다. 거기에 합이 0일 때 포인터 하나만 이동했는데 둘 다 이동시켜도 됐다.

나보다 느린 사람이 5%인거보니 정말 간당간당하게 통과했나보다...

부족한 부분을 적었더니 오류가 생긴다. 책 그대로 하면 정상동작한다;;;;;

저작자표시비영리동일조건