安监局网站建设,wordpress 修改路径,南宁经典网站建设,企业公示信息查询系统广西摘要#xff1a; Leetcode的AC指南 —— 15. 三数之和。题目介绍#xff1a;给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且… 摘要 Leetcode的AC指南 —— 15. 三数之和。题目介绍给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。 文章目录 一、题目二、解析1、哈希法2、双指针 3、思考 一、题目 题目介绍 给你一个整数数组 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 。示例 2:
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。提示 3 nums.length 3000 -105 nums[i] 105 二、解析 1、哈希法
public static ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();Arrays.sort(nums); // 对数组排序// 找出a b c 0// a nums[i], b nums[j], c -(a b)for (int i 0; i nums.length; i) {if (nums[i] 0) {break;}// 对a去重if (i 0 nums[i] nums[i - 1]) {continue;}SetInteger set new HashSet();for (int j i 1; j nums.length; j) {// 对b去重, 由于存在b c所以在对b去重时排除nums [-1,-1,0,1,-4,0,2,2,22]这种情况避免出现两次【-422】if (j i 2 nums[j] nums[j - 1] nums[j - 1] nums[j - 2]) {continue;}// 如果set中存在c则将abc存入result// 如果set中不存在c添加c到setint c - (nums[i] nums[j]);if (set.contains(c)) {result.add(Arrays.asList(nums[i], nums[j], c));set.remove(c); // 对c去重复} else {set.add(nums[j]);}}}return result;}
时间复杂度: O(n^2)空间复杂度: O(n)额外的 set 开销
2、双指针
动画效果如下
public static ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();Arrays.sort(nums); // 对数组排序int right, left;// a b c 0for(int i 0; i nums.length - 2; i){if(nums[i] 0 || nums[nums.length - 1] 0) break; // 最小值大于0最大值小于0时不满足题意直接跳出循环if(i 0 nums[i] nums[i - 1]) continue; // 对a去重复left i 1; // 左指针指向a后的第一个元素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]));// 去重逻辑应该放在找到一个三元组之后对b 和 c去重while (right left nums[right] nums[right - 1]) right--; // 左移指针指向第一个相邻不重复的元素右侧while (right left nums[left] nums[left 1]) left; // 右移指针指向第一个相邻不重复的元素的左侧right--; // 右指针指向第一个相邻不重复的元素left; // 左指针指向第一个相邻不重复的元素/*while (right left) {right--;if(nums[right] ! nums[right 1]) break;} // 左移指针指向第一个相邻不重复的元素while (right left nums[left] nums[left - 1]) left; // 右移指针指向第一个相邻不重复的元素*/}}}return result;}时间复杂度: O(n^2)空间复杂度: O(1)
3、思考 两数之和可以用双指针法吗两数之和的题目链接
答 是不可以的。两数之和要求返回数组索引下标而双指针法要求排序一旦排序后原数组的索引下标就改变了。如果两数之和也是返回数值的话就可以使用双指针了。
