[Python] #18. 4Sum(Medium)

문제 :

이 문제는 15,16 번 문제와 매우 유사하다. 사실 거의 같다 ㅋㅋ 

hellocho.tistory.com/247?category=908052

hellocho.tistory.com/248?category=908052

[Python] 15. 3Sum(Medium)

이 문제의 해결 방법은.. three sum에서는 2개의 pointer를 이용했다면... 요번에는 3개의 pointer를 이용했다.

class Solution:
    def fourSum(self, nums, target: int) :
        res = []
        nums.sort()
        for idx, a in enumerate(nums):
            if idx > 0 and a == nums[idx-1]:
                continue
            l1,r = idx +1,len(nums)-1
            while l1 < r :
                l2,r = l1 +1 ,len(nums) -1
                while l2<r :
                    four_sum = a + nums[l1] + nums[l2] + nums[r]
                    if four_sum > target :
                        r -=1
                    elif four_sum < target:
                        l2 +=1
                    else:
                        res.append([a,nums[l1],nums[l2],nums[r]])
                        l2 +=1
                        while nums[l2] == nums[l2-1] and l2<r :
                            l2 +=1
                l1 +=1 
                while nums[l1] == nums[l1-1] and l1<r :
                    l1 +=1
                
        return res

l1,l2,r이라는 포인터를 사용했다. 

결과.

688ms(O(n^3)), 13.8MB로 통과!