当前位置：首页 > article >正文

Leetcode Hot 100刷题记录 -Day5（双指针）

article 2024/11/15 17:04:39

三数之和

问题描述：

给你一个整数数组 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 

//hot6:三数之和
public class hot6_threeSum {
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> list = new ArrayList<>();
        //数组排序
        Arrays.sort(nums);
        //k为第一个指针，目的将三数之和转化为两数之和
        for(int k = 0; k < nums.length-2; k++){
            if (nums[k]>0){
                break;
            }
            if(k>0 && nums[k]==nums[k-1]) continue;
            //i和j分别为k的下一个指针和末尾指针
            int i =k+1;
            int j = nums.length-1;

            while (i < j){
                int sum = nums[k]+nums[i]+nums[j];
                if(sum < 0){
                    while(i<j && nums[i] == nums[++i]);//&&为短路与，即当前面为false时直接跳出循环，不会再判断后面
                    //nums[i] == nums[++i])的意思为：假设当先的i为1，那么nums[i] = nums[1]；然后将i=i+1=2；最后判断nums[1]和nums[2]是否相等，即++i是将i先加1再比较，这是i在后面执行时已经变为2
                } else if (sum > 0) {
                    while (i<j && nums[j] == nums[--j]);
                }
                else {
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return list;
    }
}


//带有输入输出
//hot6：三数之和
//hot6：三数之和
import java.util.*;

public class hot6_threeSum {
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> list = new ArrayList<>();
        //数组排序
        Arrays.sort(nums);
        //k为第一个指针，目的将三数之和转化为两数之和
        for(int k = 0; k < nums.length-2; k++){
            if (nums[k]>0){
                break;
            }
            if(k>0 && nums[k]==nums[k-1]) continue;
            //i和j分别为k的下一个指针和末尾指针
            int i =k+1;
            int j = nums.length-1;

            while (i < j){
                int sum = nums[k]+nums[i]+nums[j];
                if(sum < 0){
                    //防止出现重复的三位数
                    while(i<j && nums[i] == nums[++i]);//&&为短路与，即当前面为false时直接跳出循环，不会再判断后面
                    //nums[i] == nums[++i])的意思为：假设当先的i为1，那么nums[i] = nums[1]；然后将i=i+1=2；最后判断nums[1]和nums[2]是否相等，即++i是将i先加1再比较，这是i在后面执行时已经变为2
                } else if (sum > 0) {
                    //防止出现重复的三位数
                    while (i<j && nums[j] == nums[--j]);
                }
                else {
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));
                    //防止出现重复的三位数
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return list;
    }

    public static void main(String[] args){
        hot6_threeSum hot6ThreeSum = new hot6_threeSum();
        int[] nums = {-2,-2,-2,3,4,-1,0};
        System.out.println("输入：nums = " + Arrays.toString(nums));
        List<List<Integer>> result = hot6ThreeSum.threeSum(nums);
        System.out.println("输出：" + result);
    }
}

知识点总结:

三数之和转换为两数之和
&&(短路逻辑与):若是第一个成立，才判断第二个，若是第一个不成立，直接跳出循环
nums[i] == nums[++i])的意思为：假设当先的i为1，那么nums[i] = nums[1]；然后将i=i+1=2；最后判断nums[1]和nums[2]是否相等，即++i是将i先加1再比较，这是i在后面执行时已经变为2

查看全文

http://www.kler.cn/a/284099.html