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

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs