leetcode----三数之和图解

原题链接：https://leetcode-cn.com/problems/3sum

三数之和

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路：
采用的是双指针的办法，即固定一个值不变，从固定值右边的数组两头一起向中间循环，查找符合条件的三个数值。将三重循环降为双重循环，时间复杂度O(N²)。

①首先将数组转为有序数组。

在这里插入图片描述

②如图所示，取数组第一个元素下标为first，first后一位下标记为left，最后一个元素下标为right。

在这里插入图片描述

③外层为first的循环，内层为first不变，left和right的移位循环。
1）和为0时，左右指针都要移动，因为只移动一个，另外两个数没变，三数之和又等于0的时候一定是重复的三个数。(题目要求不能重复)

在这里插入图片描述

(图中为假设等于0的情况)

2）和不为0时，分>0,<0两种情况。>0时，右指针左移，左指针不动，目的是使三数之和稍微减小(向0靠拢)，<0则相反。

在这里插入图片描述

直到左右指针相撞(可判断的数小于3个)，跳出内层循环，到外层循环，从而进行下一个first指针的内层循环。

在这里插入图片描述

规则：
int left = first + 1;
int right = nums.length-1;

注意：不管是first，还是left，right在移位之前都会判断要移动的位置的值与当前位置的值是否相等，相等则跳过目标位置，继续移动。(目的就是防止出现重复结果)。例如上图的first为什么直接指向第三位的0。
另外，时刻注意数组越位，及时终止循环。

代码解答：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> List1 = new ArrayList();

        int first = 0;
        int left = first + 1;
        int right = nums.length-1;
        for(int i = 0; i < nums.length - 2; i++){
            if(nums.length < 3){
                break;
            }
            if(nums[first] > 0){//当第一个值>0，三数之和必大于零
                break;
            }
            if(nums[right] < 0){//当最后一个值<0，三数之和必小于零
                break;
            }

            while(left < right){//最少剩三个数
                if(nums[first] + nums[left] + nums[right] == 0){//等于0存储，左指针右移，右指针左移
                    List<Integer> list = new ArrayList();
                    list.add(nums[first]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    List1.add(list);
                    while(right > left && nums[right] == nums[right - 1]){
                        right--;
                    }
                    right--;
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    left++;
                }
                if(nums[first] + nums[left] + nums[right] > 0){//大于0，右数太大，右指针左移
                    while(right > left && nums[right] == nums[right - 1]){
                        right--;
                    }
                    right--;
                }
                if(nums[first] + nums[left] + nums[right] < 0){//小于0，左数太小，左指针右移
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    left++;
                }
                
            }
            while(nums[first] == nums[first + 1]){//第一个数相同则右移 
                if(first >= nums.length - 3)
                    break;
                first++;
            }
            first++;
            if(first > nums.length - 3)
                break;
                
            left = first + 1;
            right = nums.length-1;
            
        }
        return List1;
    }
}

代码写的不太好，时间空间都是中下游水平。/(ㄒoㄒ)/~~

最后编辑于：2020.10.19 18:31:10