[leetcode][15] 3Sum

문제 : https://leetcode.com/problems/3sum/

---

nums 배열이 주어졌을 때 3개의 수 a,b,c를 nums 배열에서 고를 때 a, b, c의 합이 0이 되는 조합의 수를 구해라.

---

https://withhamit.tistory.com/408

[BOJ][2143] 두 배열의 합

이 문제와 매우 유사하다. 

문제는 수가 2개에서 3개에서 늘어났다는 점인데 늘어난 수 1개(let, a)를 for문 한 번으로 정해두고 b+c = -a가 되는 두 수의 합의 조합을 구하면 된다.

 

배열을 오름차순 정렬한다.

앞에서부터 탐색하면서 a를 정한다. (let, 인덱스 = i)

let) j = i+1, k = n - 1. b = nums[j](범위 중 가장 작은 수), c = nums[k](범위 중 가장 큰 수)

 

when) a + b + c

 

i) 0인 경우 

정답이 가능하다. 

정답배열에 저장 후, b, c가 이전 수와 다른 수가 나올 때까지 j는 증가, k는 감소시킨다.

 

ii) 0보다 큰경우

숫자가 작아져야 하므로 k를 1감소시킨다.

 

iii) 0보다 작은 경우

숫자가 커져야 하므로 j를 1증가시킨다.

 

위 경우를 j < k를 만족할 때까지 반복시킨다.

j >= k가 되는 경우 i를 1 증가시킨다.

이 때, 조합의 수이기 때문에 a(nums[i])도 유니크하게 구해야 된다. (중복된 수가 나오면 안됨)

 

시간복잡도는 정렬하는데 O(NlogN). a+b+c 합이 0인 조합의 수를 구하는데 O(N^2)가 소요된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/15.%203Sum.cpp