三数之和

三数之和

​ leetcode上面的一道排序算法题。

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

注意：答案中不可以包含重复的三元组。

思路：

​ 先将数组进行升序排序。。。

​ 一个数组中三个元素相加为0，可以通过三个指针来进行判断。一个指针i从数组第一个元素开始自增。另外两个指针分别为left、right。

​ 让left最开始指向i的下一个元素，即left=i+1。right指向最后，即right=nums.length-1。

​ 判断此时 result = nums[i] + nums[right] + nums[left] 的值。如果result>0,由于数组是升序排序，那么说明要让result变小，则让right前移。如果result<0， 则让left右移，让值变大。 总而言之，就是让和趋近于0，直至等于0。一次循环中，直到left>=right，则循环结束。这就是为什么要让数组排序

​ 还有一个问题就是需要去重复，因为有可能会得到重复的结果。那么在下标不越界的情况下，让当前指针与前一个或者后一个值进行比较，如果相同，则结束本次循环。

​ 大概就是这个思路。代码如下

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //结果返回
        List<List<Integer>> list = new ArrayList<>();
        //对数组进行排序
        Arrays.sort(nums);
        
        //进行循环扫描
        for (int i=0; i < nums.length; i++) {
            //由于是升序排列，如果nums[i]都大于0.则不用循环了。
            if (nums[i] > 0) return list;
            
            //对nums[i]进行去重
            if (i>0 && nums[i] == nums[i-1]) continue;
            
            //定义两个指针
            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                //如果三者相加大于0
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right --;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left ++;
                } else {
                    //则说明符合要求，放入集合中
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //然后对结果进行去重
                    while (left < right && nums[right] == nums[right-1]) right--;
                    while (left < right && nums[left] == nums[left+1]) left ++;
                    
                    //right 和 left 迫近
                    left ++;
                    right --;
                }
            }
        }
        
        //返回结果
        return list;
    }
}