leetcode【哈希表—中等】07.三数之和

• 前言
• 题目
• 题解
• • NO1：双指针
  • NO2：双指针(优化)
• 参考文章

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为哈希表专题。

题目来源leetcode

leetcode地址：15. 三数之和，难度：中等。

题目描述(摘自leetcode)：

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

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

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]
 

提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

本地调试代码：

class Solution {

    public List> threeSum(int[] nums) {
        ...
    }

    public static void main(String[] args) {
        for (List integers : new Solution().threeSum(new int[]{-1, 0, 1, 2, -1, -4})) {
            System.out.println(Arrays.toString(integers.toArray()));
        }
    }

}

两个思路：第一种通过哈希表map来进行取值来进行比对，较麻烦，并且需要保存好对应三数的下标。第二种就是通过双指针的方式来进行同时三数之和操作。

核心条件：①a + b + c = 0。 ②和为 0 且不重复的三元组。③返回出来的是各个下标。

思路： 根据条件①说明子数组之和>0，此时我们可直接对nums数组来进行升序排序，为之后进行剪枝作准备。排序之后，来遍历每个元素i，在该过程中定义双指针left、right，一个指向遍历元素后，另一个指向最后一个元素，三个指针分别指向三个数，接着来进行依次比对操作，具体见下图：这里直接引用 代码随想录— 第15题. 三数之和题解中的图

代码：

public List> threeSum(int[] nums) {
    List> result = new ArrayList<>(nums.length);
    //例如：-1, 0, 1, 2, -1, -4  => -4,-1,-1,0,1,2
    Arrays.sort(nums);
    //三指针(指向三个数)：i、left、right
    for (int i = 0; i < nums.length;i++) {
        if(nums[i]>0){
            return result;
        }
        //与上次数一致，这里就不需要进行重复向后比对了,这里i>0仅仅是避免i=0时与i=-1的比较
        if(i>0 && nums[i] == nums[i-1]){
            continue;
        }
        int left = i+1;
        int right = nums.length - 1;
        while(left 0){
                right--;
            }else if(sum < 0){
                left++;
            }else{
                result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                //左右两指针前后各自进行过滤掉相同值情况，避免作重复操作，紧扣题目要求：不重复的三元组
                while(left 
 

 
 
NO2：双指针(优化) 
NO1的题解击败了85.86%，接着我就去看了效率最高的题解，然后对之前的代码进行改动，进行提前剪枝以达到优化的效果。
 
改动的部分在下面已经添加注释。
 
public List> threeSum(int[] nums) {
    List> result = new ArrayList<>(nums.length);
    Arrays.sort(nums);
    //改动1：i < nums.length-2，区间范围减小
    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) {
            return result;
        }
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        //改动2：提前进行剪枝
        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
            break;
        }

        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                left++;
                right--;
            }
        }
    }
    return result;
}
 
 

 
 
参考文章 
[1]. leetcode题解
 
[2].  代码随想录—第15题. 三数之和
 
 
 
 
我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！
 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料
 Q群：851968786 我们可以一起探讨学习
 注明：转载可，需要附带上文章链接