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.
Note: 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] ] public class Solution { public List<List<Integer>> threeSum(int[] num) { Arrays.sort(num); List<List<Integer>> res = new LinkedList<>();//保证输出的顺序就是插入的顺序 for (int i = 0; i < num.length - 2; i++) {//比如：{-4, -1, -1, 0, 1, 5 ,5},最后一次比较的是1,5,5 //if(i > 0 && num[i] == num[i - 1])) continue ; //这样也行 if (i == 0 || (i - 1 >= 0 && num[i] != num[i - 1])) {//比如-1只能做基准1次，后面的-1直接跳过 int low = i + 1; int high = num.length - 1;//最后一次num[i] = 1,num[low] = 5,num[high] = 5 while (low < high) { if (num[i] + num[low] + num[high] == 0) { res.add(Arrays.asList(num[i], num[low], num[high])); while (low < high && num[low] == num[low + 1]) low++;//比如：{-4, -1, -1, 0, 1, 5 ,5}，-1只能计算一次，不然会有重复 while (low < high && num[high] == num[high - 1]) high--;//比如：{-4, -1, -1, 0, 1, 5, 5}，5只能计算一次，不然会有重复 low++; high--; } else if (num[i] + num[low] + num[high] < 0) { low++; } else high--; } } } return res; }//threeSum }313 / 313 test cases passed. Status: Accepted Runtime: 77 ms Your runtime beats 87.59 % of java submissions.
Time Complexity: O( N log N ) for sorting + O (N^2) {i.e., seaching at N-i-1 nodes for i=0 to N-3}.
--------
方法2: 不用排序
先用for确定元素a，再把剩下的不重复的元素集合按照2sum方法求和-a即可。
LeetCode 1. Two Sum--数组中两元素相加为该数值，输出对应的两个索引
