3 sum
First, 2 sum is needed.
/** first sort, then search target
* actually, the problem is as the same as search a target in Young matrix
* Notice: repeated number
*/
public class Solution {
private ArrayList<ArrayList<Integer>> twoSum(int[] num, int startIndex, int target) {
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
int low = startIndex;
int high = num.length - 1;
while (low < high) {
int sum = num[low] + num[high];
if (sum < target) {
while (++low < high && num[low] == num[low - 1]);
} else if (sum > target) {
while (--high > low && num[high] == num[high + 1]);
} else {
ArrayList<Integer> pair = new ArrayList<Integer>();
pair.add(num[low]);
pair.add(num[high]);
rst.add(pair);
while (++low < high && num[low] == num[low - 1]);
while (--high > low && num[high] == num[high + 1]);
}
}
return rst;
}
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
Arrays.sort(num);
for (int i = 0; i < num.length - 2;) {
ArrayList<ArrayList<Integer>> twoSum = twoSum(num, i + 1, -num[i]);
for (ArrayList<Integer> pair : twoSum) {
pair.add(0, num[i]);
rst.add(pair);
}
while (++i < num.length - 2 && num[i] == num[i - 1]);
}
return rst;
}
}
