leetcode 15.三数之和

原题如下

https://leetcode-cn.com/problems/3sum/

题解

方法一

此方法的先对数组进行排序，然后从左到右，先确定第一个数，也就是最小的数one。先判断one大于0的时候就可以输出答案，因为三个数和为0的时候，最小的数肯定是小于等于0的。临时确定one，我们要开始照第二、三个数字two和three，起初的two确定的是one右边第一个数字，three是最后第一个数字，三数字和，he为0时，输出组合并继续进行two和three的找寻。在进行每一轮找寻时，看看two往右或者three往左是不是重复的，是则移动到下一个。直到不是重复为止。另外he的值大于或者小于0，two或者three要进行相应移动才行，当然上述小循环中有two<three，否则就要进行大循环下一轮。说一下，每个大轮确定one时，也要不能重复哦。
本思路java实例：

/*参考lc用户 @guanpengchn 的解法
 *@v7fgg
 *执行用时 :23 ms, 在所有 Java 提交中击败了83.18%的用户
 *内存消耗 :43.9 MB, 在所有 Java 提交中击败了98.11%的用户
 *2020年6月10日 14:25
 */
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        if(nums.length>2){
            Arrays.sort(nums);
            for(int one=0;one<nums.length-2;one++){
                if(nums[one]>0){break;}//最小的数大于零，和不会为0
                if(one>0&&nums[one-1]==nums[one]){continue;}
                //以这个数字为首位的所有组合都已经考虑过了
                int two=one+1;
                int three=nums.length-1;
                while(two<three){
                    int he=nums[one]+nums[two]+nums[three];
                    if(he==0){
                        ans.add(Arrays.asList(nums[one],nums[two],nums[three]));
                        while(two<three&&nums[two]==nums[two+1]){two++;}
                        while(two<three&&nums[three]==nums[three-1]){three--;}
                        //以这俩数字为第二、三个数的组合已经考虑过了
                        //为了在进行下一次判断之前就剔除重复
                        two++;
                        three--;
                    }
                    else{
                        if(he>0){three--;}
                        else{two++;}
                    }
                }
            }
        }
        return ans;
    }
}

参考资料：https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/