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

本文主要是介绍Leetcode Hot 100刷题记录 -Day5（双指针），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

三数之和

问题描述：

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

这篇关于Leetcode Hot 100刷题记录 -Day5（双指针）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---