Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero.
Note:
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. For example, given array S = {-1 0 1 2 -1 -4},A solution set is:(-1, 0, 1)(-1, -1, 2)
第一想法肯定是三层循环遍历的，时间复杂度O(n^3)，，但是做过了了Two Sum，感觉瞬间可解，随用hashtable的方法：
public List<List<Integer>> threeSum1(int[] num) {List<List<Integer>> lists = new ArrayList<>();HashMap<Integer, Integer> hash = new HashMap<>();for (int i = 0; i < num.length; i++) {hash.put(num[i], i);}for (int i = 0; i < num.length; i++) {for (int j = i+1; j < num.length; j++) {if (hash.get(0-num[i]-num[j]) != null && num[i] <= num[j] && num[j] <= 0-num[i]-num[j]) {List<Integer> list = new ArrayList<>();list.add(num[i]);list.add(num[j]);list.add(0-num[i]-num[j]);lists.add(list);}}}return lists;}时间复杂度应该在O(n^2)，但是不幸，直接超时!看着题意，需要在O(n)解决么？经分析，肯定不行，至少也要O（NlgN）。好吧，联想起排序的复杂度，所以，看是还是先把数组给排序了比较好控制。
先上代码：
public List<List<Integer>> threeSum(int[] num) {List<List<Integer>> lists = new ArrayList<>();Arrays.sort(num);for (int i = 0; i < num.length – 2; i++) {if (i == 0 || (i > 0 && num[i] != num[i-1])) {int low = i+1, high = num.length-1, sum = 0-num[i];while (low < high) {if (num[low]+num[high] == sum) {lists.add(Arrays.asList(num[i], num[low], num[high]));while (low < high && num[low] == num[low+1]) {low ++;}while (low <high && num[high] == num[high-1]) {high –;}low++;high–;} else if (num[low] + num[high] < sum) {low++;} else {high–;}}}}return lists;}
先控制一个变量a，线性遍历。此时只需找出b,c满足b+c=-a即可。由于是排序好的，剩下的可以用二分查找的思想找出b.c。于是求解（注意要排除重复解！！！！）
有一种旅行，叫单车旅行。它没有奢侈准备，
