[Python] 15. 3Sum(Medium)

문제 :

이 문제는 nums 배열에서 3개의 값을 더해 0을 만들 수 있는 조합을 찾는 문제이다.

역시나.. 프로그래밍 초보인 나는 처음 이 문제를 보고... 아 for문을 3개 써서 중복이 아닌 것의 조합을 넣어야 겠다 !! 라고 생각했지만 당연히도(?) 시간 초과이다.

그렇다면 이 문제는 어떻게 접근 하면 좋을까..

2개의 pointer를 이용해서 모든 경우의 수를 찾는 방법이 가장 쉬운(?) 접근인 것 같다. 

코드는 아래와 같다. 

class Solution:
    def threeSum(self,nums):
        res = []
        nums.sort()

        for i, a in enumerate(nums):
            if i>0 and a ==nums[i-1] :
                continue
            l,r = i+1, len(nums)-1
            while l<r:
                three_sum = a + nums[l] + nums[r]
                if three_sum > 0 :
                    r -= 1
                elif three_sum < 0 :
                    l +=1
                else:
                    res.append([a,nums[l],nums[r]])
                    l +=1
                    while nums[l] == nums[l-1] and l<r:
                        l +=1
    return res

코드를 설명하자면 처음에 nums 배열을 정렬한다 (중복 여부를 쉽게 파악할 수 있고, 2개의 포인터를 사용하기 위해서 이다.)

아래 라인에서 l,r이라는 2개의 포인터를 지정한다.

target 숫자가 0 이기때문에 왼쪽과 오른쪽의 포인터를 이동하면서 값을 더해주고 값이 0과 같다면 res에 list를 추가한다.

결과.

788ms(O(n^2)), 17.3MB로 통과.