15三数之和

题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组

示例.png

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        //0.边界判断 空数组或者元素小于3个都是不符合的
       if(nums==null) return null;
       List<List<Integer>> result = new ArrayList();
       if(nums.length<3) return result;

       //1.对数组排序
       Arrays.sort(nums);
       //2.定义扫描边界 
       int lastIdx = nums.length - 3;//循环趟数 -3是因为还需要Left Right，所以要去除
       int lastR = nums.length - 1;
       //3.遍历得到想要的三元组(注意：去重)
       for(int i = 0;i <= lastIdx;i++) {

           //当前数值等于前一个数值时需要跳过，因为相同数值当首元素一次就可以了 
           if(i > 0 && nums[i] == nums[i-1]) continue;//去重

           //重置l r remain
           int l = i + 1;
           int r = lastR;
           int remain = nums[I];
           //查找以nums[i]为首元素且符合条件的三元组
           while(l < r) {
             int sum = nums[l] + nums[r];
             if((remain + sum)==0){//和 == 0
                 //添加
                 result.add(Arrays.asList(nums[i],nums[l],nums[r]));
                  //去重操作
                 while(l < r && nums[l]==nums[l+1]) l++;
                 while(l < r && nums[r]==nums[r-1]) r--;
                 //向前向后走一位
                 l++;
                 r--;
             }else if((remain + sum) > 0) {// 和 > 0
                 r--;
             }else {//和 < 0
                 l++;
             }
           }
       }

       //4.返回结果
       return result;

    }
}

执行结果.png