[LeetCode] 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.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

 

Approach

처음 했던 시도는 2Sum 문제에서 활용했던 방식인 hash를 활용하는 것이었으나

무슨 짓을 해도 time limit exception...

timeout이 나는 예제는 큰 수가 엄청 많이 들어가는 그런 input이었다.

난이도는 medium이었음에도 불구하고 정답률이 낮았던 이유가 있었음

빈 input에 주의

 

Optimization

우선 input을 sort 하고 a + b + c = 0에서 b + c = -a인점에 착안

a을 맨 처음 선택하고 b + c = -a를 만족하는 b와 c를 배열 앞, 뒤에서 찾아간다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_3Sum.cpp

chi3236/algorithm