前后指针的妙用之3 SUM

题目意思 ：

   在一个数组中,无重复元素，找出所有 组合 他们的和 == 0 即 a + b + c = 0;

   组合满足的条件 ：

     1 . a < b < c

     2 . 组合不能重复

 

题目思路：

   如果是暴力求解话，那么就得有三个for循环，时间复杂度为 O(n^3);

   而下面的方法，为O(n^2)

   首先对数组排序；

   然后可以借鉴暴力求解的方法；

   比如说，对数组 - 1 ，0， 1， 2 ；

   当 i = -1 , j = 0 , 看k = 1 或 者 k = 2 是否满足条件

   然后就是 i = -1 , j= 1 , 看 k = 2 是否满足条件

 

   这里我们就可以得出一条结论：i+j 搭配，j后的元素只可能存在一个k 使得i+j+k = 0 （数组排好序，而且无重复元素）

   如果i + j + k > 0 那么 k 之后的与 i + j 相加也必然 > 0 , 所以，此时，只能使 j , k 某个 减小 才能使得 i + j + k == 0  , 所以 k--;

   同理i + j + k < 0 因为k 是往前移的，所以只能j++,才有可能 === 0；

  

   好的算法，不会做无意义的重复的事情；

   就拿这个方法与暴力方法比较；

   对于 -1 ， 0 ，1 ，2 ，3 ， 4

   暴力 ： i = -1 , j = 0 ,  k = 1 , i + j + k == 0 , 明显对于 i = -1 , j = 0 的情况，不可能再有其他的元素使得i+j+k=0,所以接下来的k = 2 , k = 3 ,

   是完全没有必要的操作，但是暴力方法，仍然在傻乎乎的计算，所以就慢了；

  但是对于运用前后指针的方法，就不会这么傻乎乎的了，当i + j + k == 0 , 它知道对于i+j 这种情况不可能再有别的结果了，所以j++;

  那么此时 i+j + k 必然 > 0 , 所以 ， k--; 再计算，不就成功跳过了那些没意义的操作了吗？

 

实现代码 （来自DISCUSS）

 

public class Solution {
    // 三个数的和为0 看下面这种让人叹为观止的方法
    // 前后指针的妙处！
    // excellent
    public List<List<Integer>> threeSum(int[] arr) {
        List<List<Integer>>lists = new ArrayList<List<Integer>> ();
        HashSet<List<Integer>> set = new HashSet<> ();
        int len = arr.length;
        if(len < 3) return lists;
        Arrays.sort(arr);
        for(int i = 0 ; i < len - 2; i++) {
            // 定义前后指针 
            for(int j = i + 1 , k = len - 1; j < k ; ) {
                int count = arr[i] + arr[j] + arr[k];
                // (i+j) 相对k 太大
                if(count < 0) j++;
                else if(count > 0) k--;
                else {
                    List<Integer> list = new ArrayList<> ();
                    list.add(arr[i]);
                    list.add(arr[j]);
                    list.add(arr[k]);
                    if(set.add(list)) lists.add(list);
                    // 这里如果是contains就不行了，因为他会遍历这个数组进行比较
                    // if(!lists.contains(list)) lists.add(list);
                    // 对于(i + j)来说，只可能存在一个k使得他们 == 0 (无重复元素)
                    j++;
                    k--;
                }
            }
        }
        return lists;
    }    
 }

 

   其实我第一想法，是hash , 数组排序，然后遍历一边数组，把每一个元素的相反数作为key 放入，map,

   那么两层for循环遍历数组，找到所以的两个元素的组合，看他们的和是否在map,如果在，再

  进行相应的重复检查，放入lists中

    无奈超时了..........