LeetCode-15三数之和

Leefs 2020-03-01 PM 1933℃ 0条

# LeetCode-15三数之和

**题目描述**

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

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

示例

> 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
>
> 满足要求的三元组集合为：
> [
>   [-1, 0, 1],
>   [-1, -1, 2]
> ]

**题解**

这道题的难点是不能包含重复的答案，对于[0,0,0,0,0]这个数组，答案只有一个[0,0,0]。
首先我们对数组先排序一次，在排好序的数组上，就很容判断前后元素是否相当，这样可以过滤掉重复的答案。
再定义三个指针，k，i，j如下图所示

![38.LeetCode-15三数之和01.jpg][1]

指针`i`从左往右移动，且始终比`k`大一位，这样就保证不会跟`k`重叠，
指针`j`从右往左移动，且始终比`i`大，这样`i`和`j`就不会重叠，即三个指针都不会重叠。

在这个基础上，实现我们的主要逻辑：

+ 1.nums[k]>0时，可以直接跳出循环，因为nums[k]都比0大了，后面的nums[i]和nums[j]肯定更大，三者加起来肯定大于0
+ 2.nums[k]和nums[k-1]相等，即前后元素重复了，需要过滤掉
+ 3.如果nums[i]+nums[j]+nums[k]>0，即三者之和太大了，我们将j指针左移，因为三个数中最大的肯定是nums[j]，将j左移就可以减小三者之和。
+ 4.如果nums[i]+nums[j]+nums[k]<0，说明三者之和太小了，同理将i指针右移
+ 5.如果nums[i]+nums[j]+nums[k]==0，这就是要找的答案，将其保存起来，同时i右移，j左移
  i和j在移动的过程中还需要判断前后元素是否重复

![38.LeetCode-15三数之和02.gif][2]

**代码实现**

```java
public static List<List<Integer>> threeSum2(int[] nums){
    if(nums==null) {
        return new ArrayList<List<Integer>>();
    }
    ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
    int n = nums.length;
    //正式处理之前，先将数组排序
    Arrays.sort(nums);
    //假设数组为[0,1,2,3,4,5,6,7,8,9,10]
    //第三个指针k最多到下标8位置，因为后面两个位置需要留给另外两个指针
    for(int k=0;k<n-2;k++){
        //nums[k]>0，说明后面的元素肯定也大于0，最后结果肯定>0，故直接跳出
        if(nums[k]>0) {
            break;
        }
        //如果当前元素和前面一个元素一样，忽略重复元素
        if(k>0 && nums[k-1]==nums[k]) {
            continue;
        }
        //定义另外两个指针 i 和 j
        int i = k + 1;
        int j = n - 1;
        while(i<j) {
            int tmp = nums[i]+nums[j]+nums[k];
            //如果三数之和>0，说明最右边的值太大了
            if(tmp>0) {
                --j;
                while(i<j && nums[j+1]==nums[j]) {
                    --j;
                }
            }else if(tmp<0) { //如果三数之和<0，说明左边的值太小了
                ++i;
                while(i<j && nums[i-1]==nums[i]) {
                    ++i;
                }
            }else {
                //三数之和等于0，保存结果
                //同时左指针往右移动，右指针往左移动，
                //如果移动过程中碰到重复元素，则继续移动
                res.add(Arrays.asList(nums[k],nums[i],nums[j]));
                ++i;
                --j;
                while(i<j && nums[i-1]==nums[i]) {
                    ++i;
                }
                while(i<j && nums[j+1]==nums[j]) {
                    --j;
                }
            }
        }

}
    return res;
}
```

*附：原文链接地址https://leetcode-cn.com/problems/3sum/solution/dong-hua-yan-shi-15-san-shu-zhi-he-by-wang_ni_ma/*

**下方是小编的代码**

很暴力，运行超时

```java
//太暴力，运行超时
public static List<List<Integer>> threeSum(int[] nums){
    Arrays.sort(nums);
    //List<List<Integer>> list = new ArrayList<>();
    Set<List<Integer>> result = new LinkedHashSet<>();
    for(int i=0;i<nums.length-2;i++){
        for(int j=i+1;j<nums.length-1;j++){
            for(int k=j+1;k<nums.length;k++){
                if(nums[i]+nums[j]+nums[k] == 0){
                    result.add(Arrays.asList(nums[i],nums[j],nums[k]));
                }
            }
        }
    }
    return new ArrayList<>(result);
}
```

[1]: https://lilinchao.com/usr/uploads/2020/03/2453946507.jpg
  [2]: https://lilinchao.com/usr/uploads/2020/03/1473873459.gif

标签: LeetCode刷题

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/663.html

上一篇 Java实现RSA加密与解密

下一篇线程通信之传统版生产者消费者模式

LeetCode-15三数之和

评论已关闭

栏目分类

标签云

友情链接申请

LeetCode-15三数之和

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请