[알고리즘] 4Sum

2021.07.15 - [알고리즘] - [알고리즘] Valid Triangle Number

[알고리즘] Valid Triangle Number

포인트

• 만약 1년 전에 저였다면, 4중 for loop 를 돌고 틀려놓고 왜 틀렸을까? 라는 의문을 던졌을 텐데 지금 단계는 "아 무조건 4중 for loop 는 아닌 것 같은데"로 생각이 전환된 느낌입니다. 저는 그래서 이를 쪼개서 2중 포문 + 투 포인터 전략으로 해결하였습니다.
• 이와 같은 문제 접근 방법인 is Valid Triangle 문제도 풀어보시면 좋을 것 같습니다.
  
  

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

4Sum - LeetCode

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = set()
        nums.sort()
        for j in range(len(nums) - 3):
            for i in range(j+1, len(nums) - 2):
                left = i + 1
                right = len(nums) - 1
                # 투 포인터 전략을 사용하자
                while left < right:
                    summation = nums[j] + nums[i] + nums[left] + nums[right]
                    if summation < target:
                        left += 1
                    elif summation > target:
                        right -= 1
                    else:
                        result.add((nums[j], nums[i], nums[left], nums[right]))
                        # 리스트는 set 에서 해쉬 처리가 되지 않기 때문에 튜플로 바꾸어서 해결하자.

                        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 list(map(list, result))