每天一题LeetCode【第13天】

T15. 3 Sum【Medium】

题目

给一个有 n 个整数的数组 S，找到 S 中的所有和为 0 的三元组（S 中元素 a,b,c 使得 a+b+c = 0 ）。

注意：解集不能包含重复的三元组。

举个例子，如果给出数组 S = [-1, 0, 1, 2, -1, -4],

一个解集是
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

具体可以看代码注释~

代码

代码取自 Top Solution，稍作注释

public List<List<Integer>> threeSum(int[] num) {
    //调用方法对它进行排序
    Arrays.sort(num);
    //新建一个List，泛型是泛型为Integer的List
    List<List<Integer>> res = new LinkedList<>(); 
    //主要代码
    for (int i = 0; i < num.length-2; i++) {
        //num[i] != num[i-1]来排除重复
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            //先把num[i]取反，然后通过lo,还有hi的移动来确定结果
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                //相等时
                if (num[lo] + num[hi] == sum) {
                    //添加入res
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    //通过while num[lo] == num[lo+1] 跳过重复的
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    //在sum相同时当前lo和hi都不可能了，于是同时向内移动一个
                    lo++; hi--;
                }
                //若和小于sum,则和要增加，所以lo++ 
                else if (num[lo] + num[hi] < sum) lo++;
                //若和大于sum,则和要减少，所以hi-- 
                else hi--;
           }
        }
    }
    return res;
}

补充

List 中的泛型：

为什么要说这个呢，因为题中的 List<List<Integer>> 就用到了泛型

例如List<E>，这其中 E 表示 List 集合中元素的类型。

其中 E 可以是 int,String,也可以是自己写的类，在处理一类的数据时总是可以用到，比如安卓的ListView