1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: 3Sum
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/3sum/
7+ Notes:
8+ Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
9+ Find all unique triplets in the array which gives the sum of zero.
10+ Note:
11+ Elements in a triplet (a,b,c) must be in non-descending order. (ie, a <= b <= c)
12+ The solution set must not contain duplicate triplets.
13+ For example, given array S = {-1 0 1 2 -1 -4},
14+ A solution set is:
15+ (-1, 0, 1)
16+ (-1, -1, 2)
17+
18+ Solution: Simplify '3sum' to '2sum' O(n^2). http://en.wikipedia.org/wiki/3SUM
19+ */
20+ public class Solution {
21+ public List <List <Integer >>threeSum (int []num ) {
22+ List <List <Integer >>res =new ArrayList <List <Integer >>();
23+ Arrays .sort (num );
24+ int N =num .length ;
25+ for (int i =0 ;i <N -2 &&num [i ] <=0 ; ++i )
26+ {
27+ if (i >0 &&num [i ] ==num [i -1 ])
28+ continue ;// avoid duplicates
29+ int twosum =0 -num [i ];
30+ int l =i +1 ,r =N -1 ;
31+ while (l <r )
32+ {
33+ int sum =num [l ] +num [r ];
34+ if (sum <twosum ) ++l ;
35+ else if (sum >twosum ) --r ;
36+ else {
37+ ArrayList <Integer >tmp =new ArrayList <Integer >();
38+ tmp .add (num [i ]);tmp .add (num [l ]);tmp .add (num [r ]);
39+ res .add (tmp );
40+ ++l ; --r ;
41+ while (l <r &&num [l ] ==num [l -1 ]) ++l ;// avoid duplicates
42+ while (l <r &&num [r ] ==num [r +1 ]) --r ;// avoid duplicates
43+ }
44+ }
45+ }
46+ return res ;
47+ }
48+ }
