LeetCode100之三数之和(15)--Java

1.问题描述

        给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

        注意

        答案中不可以包含重复的三元组

        示例1

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

        示例2 

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

        示例3 

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

        提示

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

        难度等级

             中等

        题目链接

             三数之和

2.解题思路

        这道题叫做三数之和，可以看做两数之和的升级版，不过我没办法用两数之和的hash方法来做了。这一次，我选择了双指针遍历。可能你会疑惑，不是三数之和吗？怎么是双指针法，其实我们只要把其中一个数固定下来，那不就是回归两个数了吗?两个数当然就是双指针法了。

        首先，我们得定义一个List集合来存储结果，还要对数组进行排序(使用双指针法的前提)。

    //用来存储结果List<List<Integer>> result = new ArrayList<>();

        接着，我们就可以开始数组的遍历了。for循环先固定第一个数，这里固定数也是有讲究的，因为它要求的是三个数和为0。我们已经对数组进行排序了，所以小的数肯定在前面，大的数肯定在后面，如果我们的第一个数就已经大于0了，那么后面两个数必定大于0，也就不可能三个数相加为0，所以直接结束就好了。

        //第一个数就大于0，那三个数不可能加起来和为0if(nums[i] > 0){break;}

        如果，第一个数小于0且索引不为0(防止数组越界)的话，因为题目告诉我们不包含重复的三元组，所以我们的第一个数要跳过已经使用过的数。又因为我们是排好序的，所以相同的数就在数本身的前后，我们只需要判断当前的数是否和前面的那个数相等就好了，相等我们就跳过，避免重复。

        //除去相同的整数if(i > 0 && nums[i] == nums[i-1]){continue;}

        经过两轮排查之后，我们终于固定下来了第一个数，剩下的两个数我们就要从第一个数后面开始找了。定义左右两个指针，左指针从第一个数旁边开始向后走，右指针从数组的末端向前走，一个在可选范围内最小，一个在可选范围内最大。然后两个指针尝试靠拢，每一次移动，都计算一下三数之和是否为0。

        //左右指针相互靠拢int left = i+1;int right = nums.length - 1;

        如果三数之和大于0，说明加多了，右指针所指的数较大，要将右指针往左移，减小一点；如果三数之和小于0，说明加少了，左指针所指的数较小，要将左指针往右移；如果三数之和等于0，那么就将这是哪个数存入一开始定义的List集合中。

            //计算当前的三数之和int sum = nums[i] + nums[left] + nums[right];if(sum > 0){//sum > 0,说明加多了，右指针要往左移right--;continue;}else if(sum < 0){//sum < 0 ,说明加少了，左指针要往右移left++;continue;}//若走到这一步，说明三数之和为0List<Integer> data = new ArrayList();data.add(nums[i]);data.add(nums[left]);data.add(nums[right]);result.add(data);

        找到一组三数之和后，不要着急着找第二组，因为题目要求不能有重复的三元组，所以我们还要将左右指针旁边与它们相同的数先跳过之后，再找下一组。

//跳过与左指针相同的整数while(left < right && nums[left] == nums[left + 1]){left++;}//跳过与右指针相同的整数while(left < right && nums[right] == nums[right- 1]){right--;}

        让左右指针不断靠拢，直到左右指针相遇，找到我们所固定的第一个数的所有可能。

            //左右指针继续靠拢left++;right--;

        之后重复上述操作，再重新固定一个新的数，左右指针继续移动找到将所有的数遍历完或者遇到第一个数大于0的情况退出循环，我们就找到了我们想要的所有结果。

3.代码展示

class Solution {public List<List<Integer>> threeSum(int[] nums) { //用来存储结果List<List<Integer>> result = new ArrayList<>();//对整数数组进行排序Arrays.sort(nums);for(int i = 0;i < nums.length;i++){//第一个数就大于0，那三个数不可能加起来和为0if(nums[i] > 0){break;}//除去相同的整数if(i > 0 && nums[i] == nums[i-1]){continue;}//左右指针相互靠拢int left = i+1;int right = nums.length - 1;while(left < right){//计算当前的三数之和int sum = nums[i] + nums[left] + nums[right];if(sum > 0){//sum > 0,说明加多了，右指针要往左移right--;continue;}else if(sum < 0){//sum < 0 ,说明加少了，左指针要往右移left++;continue;}//若走到这一步，说明三数之和为0List<Integer> data = new ArrayList();data.add(nums[i]);data.add(nums[left]);data.add(nums[right]);result.add(data);//跳过与左指针相同的整数while(left < right && nums[left] == nums[left + 1]){left++;}//跳过与右指针相同的整数while(left < right && nums[right] == nums[right- 1]){right--;}//左右指针继续靠拢left++;right--;}}return result;}
}

4.总结

        我觉得这道题的难点就在于能不能想到将数组进行排序和把一个数固定下来，将三数之和简化为两数之和。一旦想到之后，采用左右指针获取所有结果这些操作都不难想到了。同时还要记得要跳过那些相同的整数。好了，这道题就bb到这了，祝大家刷题愉快~