[파이썬 인터뷰 알고리즘] 세 수의 합

 

 

졸리담..

github.com/onlybooks/algorithm-interview

---

15. 3Sum

 

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

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]]

---

3Sum - LeetCode

 

1. 가장 쉽게 접근 => O(n^3) ..! , 딱봐도 너무 심하다.. 

2. 쓰리 포인트로 풀어보기

중복값이 발생할 수 있으므로 continue를 이용하여 건너띈다.

이것은 [ n1, n2, n3] 의 결과를 각각 i, j, k로 담아야하는데, i값이 이전과 같으면 중복 결과를 던져줄 수 있기때문이다. 

즉, 같은 경우는 넘겨야한다. 

이 경우는 당연히 시간초과가 난다. 

 

onlybooks/algorithm-interview

3. 투포인터로 풀어보기

 

onlybooks/algorithm-interview

 

아래와 같이 sum>0 경우엔 오른쪽으로 반대는 왼쪽으로 이동해야한다. (sort가 되어있어야 한다)

else문에 있는 while문은 중복값을 처리하기 위한 코드이다. 

 

정말 어렵다... 😔 이렇게 풀이보고 코드보면 이해가 되지만, 내 스스로 생각해야하는데. 정말 그런 날이 오겠지? 

말이 🌱이 되니까 온다고 생각해야겠다 ㅎㅎ

 

책에서 소개해준 내용을 몇가지 보니까 투포인터가 정말 중요하고 문제 풀이의 시간을 줄이는데 유용하다는 생각이 많이든다.

 

* 투포인터는 주로 정렬된 배열에서 이용하는 것이 좋다.