做相册网站推荐,开发小程序外包公司,百度快速查询,做网站时最新菜品的背景图一、原题
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元组。…一、原题
给你一个整数数组 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 。
二、心得 这题我的第一反应就是三个 for() 循环依次向后遍历找到符合的三元解并将它们存入列表中并返回结果。可这样一来感觉挺怪的说不出的感觉~ 于是乎我参考了一下他人的解法当我看到 Arrays.sort(nums); 时灵光乍现一个新的思路从我脑海中闪过直接用下图来解释我的思路 于是乎有了下面的代码看注释能看懂的~
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums); // 思考一下为什么要排序ListListInteger a new ArrayListListInteger(); // 创建返回值——一个包含列表的列表// 三元数的第一个数的指针指向数组的开始即nums[0]向后遍历nums[i]for(int i 0; i nums.length; i ){// 向后遍历的过程中若遇到相同的数字则循环下一次跳过当前的循环否则继续执行if(i 0 nums[i] nums[i - 1]){continue;}// 三元数的第三个数的指针指向数组的末端即nums[nums.length - 1]向前遍历nums[j]int j nums.length - 1;// 三元数的第二个数的指针指向数组的 nums[i 1]向后遍历nums[k]保持第二个数始终在第一个数后面for(int k i 1; k nums.length; k ){// 向后遍历的过程中若遇到相同的数字则循环下一次跳过当前的循环否则继续执行if(k i 1 nums[k] nums[k - 1]){continue;}// 如果当前的三个数相加大于0说明正数 nums[j] 过于大了好好想想则第三个数应该向前遍历while(k j nums[i] nums[k] nums[j] 0){j --;}// 如果第三个数向前遍历都与第二个数重合了则跳出当前的循环if(k j){break;}// 如果当前的三个数相加等于0则找到了一组三元解将满足条件的三元数组存入结果的列表中if(nums[i] nums[k] nums[j] 0){ListInteger list new ArrayListInteger();list.add(nums[i]);list.add(nums[k]);list.add(nums[j]);a.add(list);}}}return a;}
} 这里解答一下为什么要排序因为从小到大排序可以肯定的是这里首先把 [0, 0, 0] 的情况排除掉nums[0] 一定为负nums[nums.length - 1]一定为正这样有利于我们去判断三者相加的情况即对应代码中的 nums[i] nums[k] nums[j] 0 看看注释~。 这样一下来时间复杂度就从连续三重 for() 的 降为了也算是节约了计算机的资源了噻~
