三数之和

摘要

两数之和已经解决了，那三数之和能不能用同样方法解决尼？？？？？

# 三数之和

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

2. 示例描述：

- 示例一：
     - 输入：nums = [-1,0,1,2,-1,-4]
     - 输出：[-1,0,1],[-1,-1,2]

- 示例二：
     - 输入：nums = [2,4,3,-5,1]
     - 输出：[2,3,-5],[4,1,-5]

3. 解题思路：本题的解题使用双指针解法，也可以使用暴力解法，但是暴力解法导致一个问题，就是结果集中出现重复的结果，去重比较麻烦，这里使用双指针的解法。

首先对数组进行排序(从小到大，或者从大到小排序都行)，然后固定一个值(即为数组循环下标i所指向的数组的值)，然后定义两个双指针（left和right），一个指向数组的尾部(即为right所指向的)，一个指向与当前循环i所指向值不同的位置(即为left所指向的)，然后这三个指针所指数组的值的和是否为0，如果为0就将这三个数加入结果集合中，否则继续寻找满足条件的结果集合。具体代码实现以及详细解释去重的过程，见以下代码以及注释。

4. 代码实现：

```java
    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,
               // 那么之后的两个数与i下标所对应的值之和肯定不等于0
               //于是直接返回
               if (nums[i] > 0) {
                   return result;
               }
               //这是去重的方式(解释):
               //首先i>0，是为了防止i-1数组下标越界的问题
               //为什么nums[i]==nums[i-1]要continue尼
               //因为举个栗子[1,1,1,-2],如果不排除相同的数，那么结果为:
               //[1,1,-2](数组下标为0，1，3),[1,1,-2](数组下标为[1,2,3])
               //最终结果重复了，就不能达到去重的效果
               if (i > 0 && nums[i] == nums[i - 1])
                   continue;
               //双指针解法开始
               //一个指向 不与遍历下标i相同的值的left下标
               //另一个指向数组尾部
               int left = i + 1;
               int right = nums.length - 1;
               while (left < right) {
                   //三个指针指向数组的值的和大于0
                   //说明和大于0时,那说明有右指针指向的值大了，需要向左迁移(数组从小到达排过序的)
                   if (nums[i] + nums[left] + nums[right] > 0) {
                       right--;
                   }
                   //三个指针指向数组的值的和小于0
                   //说明和小于0时,那说明左指针指向的值小了，需要向右迁移(数组从小到达排过序的)
                   else if (nums[i] + nums[left] + nums[right] < 0) {
                       left++;
                   }
                   //如果三个指针指向的值的和刚好为0,那么找到一组解
                   //加入结果集中
                   if (nums[i] + nums[left] + nums[right] == 0) {
                       List<Integer> temp = new ArrayList<>();
                       temp.add(nums[i]);
                       temp.add(nums[left]);
                       temp.add(nums[right]);
                       result.add(temp);
                       //继续去重
                       //为什么这里还需要去重
                       //举个栗子为先:
                       //nums=[-2,-1,-1,-1,0,0,1,1]
                       //当i指向下标为1的位置时，left指向下标为4的位置,right指向下标为7的位置
                       //结果刚好为0，即为[-1,0,1],如果不进行这一步操作，
                       //那么while循环中会继续从下标为i=1,left = 5，right =6，
                       //结果刚好为0,即为[-1,0,1]，于上一步操作结果相同，达不到去重的效果
                       while (right > left && nums[right] == nums[right - 1]) right--;
                       while (left < right && nums[left] == nums[left + 1]) left++;
                       //去重结束(以上为局部去重)。
   
                       //如果找到一组结果，为了找到下一组结果，左指针右移动，右指针左移动
                       //为什么不单独移动一个指针，为什么两个指针都要移动尼？
                       //解答:因为数组已经排过顺序了(前提),而且上一步已经去重了,
                       //并且(三个指针所指向的值)三个数之和已经为0,那么只移动一个指针，不管是左指针右移动，还是右指针左移动
                       //三个数的结果肯定不为0,(因为左指针右移动，右指针不变，而i所指向的值不变，那么结果肯定大于0)
                       //如果右指针左移动，左指针不变，i所指向的值不变，那么三个数之后肯定小于0.
                       //所以左指针右移动，右指针左移动，才有可能会得到三个数之和为0
                       //到此解答完毕
                       left++;
                       right--;
                   }
               }
           }
           //返回最终结果
           return result;
       }
   ```

三数之和

摘要

您还没有登录,登录后即可评论

评论