3Sum
3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
Solution:
First sort the array S. For each element, figure out the two-sum problem.
Use hash table or something like that to avoid duplicate triplets.
Complexity is sorting O(nlogn) plus n two-sum problem nO(n) = O(n^2).
The following code passes LeetCode online large judge.
Comments
Post a Comment