[Leet code] 15. 3Sum

Category	ps/브루트 포스
Tag	브루트 포스
Tags	two pointer
난이도	★★
발행 여부
사이트	Leet code
실수 유형
이해	어느정도 이해
최종 편집 일시	@2021년 11월 14일 오후 8:44
푼 날짜	@2021년 11월 14일 오후 8:04

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드 (브루트 포스)

풀이 코드 (책) two pointer

퇴고

문제 해설 및 주의사항

원문

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

번역 및 주의사항

같지 않은 세 수 i, j, k 에 대해서 nums[i] + nums[j] + nums[k] == 0 인 모든 triplet 을 반환해라.

Constraints:

• 0 <= nums.length <= 3000

• 105 <= nums[i] <= 105

---

풀이

• 브루트 포스?
  • 브루트 포스는 $O(n^3)$ 에 문제를 풀 수 있을 것이다.
  • 3000^3 = 27억. 아마 시간 초과 할 것이다.

• 투 포인터

내 풀이 코드 (브루트 포스)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        answer = []
        nums.sort()        
        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:
                        answer.append([nums[i],nums[j],nums[k]])
        return answer

풀이 코드 (책) two pointer

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        answer = []
        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:
                    right -= 1
                elif sum < 0:
                    left += 1
                else:
                    # 정답 처리
                    answer.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, right 진행
                    left += 1
                    right -= 1

                    
        return answer

• two pointer 사용
  • nums 를 오름차순 정렬한다.
  • i 를 기준으로 0 부터 nums - 2 길이 까지 순회한다.
    • i + 1 부터 nums - 2 를 left 와 right 이 순회한다.
    • 현재 sum 이 양수라면, 값을 줄여야 하므로, right 을 -1 한다.
    • 현재 sum 이 음수라면, 값을 늘려야 하므로, left 를 +1 한다.
    • 현재 sum 이 0이라면, 정답이므로, 정답처리한다.
      • 현재 i 에서 더 많은 답이 있을 수 있다.
      • left, right 시점에서 앞에 중복된 값이 있으면 건너뛴다.
      • 반복

---

퇴고

💡

계속 two pointer 라는 용어가 등장한다. two pointer 는 주로 정렬된 배열을 대상으로 하며, 2개의 포인터가 좌우로 자유롭게 움직이며 문제를 풀이한다. Sliding Window 와 여러모로 비슷한데, 20장에서 이 둘의 차이를 살펴보도록 하겠다.