怎么做网站论坛,三水顺德网站建设,wordpress4.9上传失败,个人主页排版推荐阅读
000-从零开始的数据结构与算法
001-01-ksum 求符合条件的 k 个数 1. Two Sum/15. 3Sum/18. 4Sum/
002-两数相加 add two numbers
003-无重复字符的最长子串 Longest Substring Without Repeating Characters
004-寻找两个正序数组的中位数
005-最长回文子串 Lon…推荐阅读
000-从零开始的数据结构与算法
001-01-ksum 求符合条件的 k 个数 1. Two Sum/15. 3Sum/18. 4Sum/
002-两数相加 add two numbers
003-无重复字符的最长子串 Longest Substring Without Repeating Characters
004-寻找两个正序数组的中位数
005-最长回文子串 Longest Palindromic Substring
006-N 字形变换 zigzag conversion
007-整数反转 reverse integer 整数的位运算汇总
008-Regular Expression Matching 正则表达式匹配 42.Wildcard Matching 通配符匹配
009-盛最多水的容器 Container With Most Water 双指针法 42. 接雨水 Trapping Rain Water 407. Trapping Rain Water II
010-删除链表的倒数第 N 个结点 Remove Nth Node From End of List 双指针
011-21.合并多个有序的链表 merge k sorted lists
012-括号生成 generate-parentheses 20. 有效的括号 valid parentheses 32. 最长有效括号 Longest Valid Parentheses
013-K 个一组翻转链表 Reverse Nodes in k-Group 24. 两两交换链表中的节点 swap nodes in pairs
014-两数相除 divide two integers
015-串联所有单词的子串 Substring with Concatenation of All Words
016-31.下一个排列 next permutation 46. 全排列 permutations 47. 全排列 II permutations-ii 60. 排列序列 permutation sequence
017-33. 搜索旋转排序数组 Search in Rotated Sorted Array 81. Search in Rotated Sorted Array II 153. Find Minimum in Rotated Sorted Array 寻找旋转排序数组中的最小值 154.Find Minimum in Rotated Sorted Array II
018-34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array
019-36. 有效的数独 Valid Sudoku 37. 解数独 sudoku solver
020-39. 组合总和 Combination Sum 40. 组合总和 II Combination Sum II 77. 组合 combinations 216. Combination Sum III 377. 组合总和 Ⅳ 1. Two Sum 两数之和
题目
给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那 两个 整数并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素不能使用两遍。
示例:
给定 nums [2, 7, 11, 15], target 9因为 nums[0] nums[1] 2 7 9
所以返回 [0, 1]思路
最简单粗暴的一个双层循环
1遍历第一层数组 nums[i]
2遍历第二层数组 nums[j]如果 nums[i] nums[j] t符合。
基础解法
java 实现
public int[] twoSumBasic(int[] nums, int target) {for(int i 0; i nums.length; i) {for(int j 0; j nums.length; j) {// 每个元素只使用一次if(i j) {continue;}if(nums[i] nums[j] target) {return new int[]{i, j};}}}// 实际每个都有答案不应该都到这里。return null;
}性能分析
可谓惨不忍睹为什么呢
是否有比较好的优化思路
Runtime: 167 ms, faster than 5.01% of Java online submissions for Two Sum.
Memory Usage: 41.3 MB, less than 10.92% of Java online submissions for Two Sum.优化解法
优化思路
借助 HashMap 数据结构将原本 O(n) 的遍历降低为 O(1) 的查询。
java 实现如下
实现时注意 HashMap 的扩容问题此处直接指定为和数组一样大。
public int[] twoSum(int[] nums, int target) {int[] result new int[2];final int length nums.length;MapInteger, Integer map new HashMap(length);for(int i 0; i length; i) {int num nums[i];int targetKey target - num;if (map.containsKey(targetKey)) {result[1] i;result[0] map.get(targetKey);return result;}map.put(num, i);}return result;
}效果
Runtime: 1 ms, faster than 99.93% of Java online submissions for Two Sum.
Memory Usage: 39.5 MB, less than 69.35% of Java online submissions for Two Sum.15. 3Sum 三数之和
结束了第一道开胃菜之后我们来看看第二道菜。
题目
给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有满足条件且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例
给定数组 nums [-1, 0, 1, 2, -1, -4]满足要求的三元组集合为
[[-1, 0, 1],[-1, -1, 2]
]粗暴解法
最简单的思路我们直接来一个三层循环
public ListListInteger threeSum(int[] nums) {if(nums.length 3) {return Collections.emptyList();}ListListInteger results new ArrayList();SetString stringSet new HashSet();for(int i 0; i nums.length-2; i3) {for(int j i1; j nums.length-1; j) {for(int k j1; k nums.length; k) {if((nums[i] nums[j]nums[k]) 0) {ListInteger list Arrays.asList(nums[i], nums[j], nums[k]);// 排序保证结果不重复Collections.sort(list);String string list.toString();if(stringSet.contains(string)) {continue;}stringSet.add(string);results.add(list);}}}}return results;
}执行结果
很不幸这个是不通过的。会执行超时因为执行的比较慢。
优化解法
优化思路
1对原始数组进行排序保证可以使用双指针法
2固定 1 个元素。剩余的两个元素采用双指针的方式。初始化时一个在最左边一个在最右边。然后不断调整位置直到符合条件为止。
3不可以包含重复的三元组要同时跳过重复的信息。
java 实现
public ListListInteger threeSum(int[] nums) {//1. 排序Arrays.sort(nums);ListListInteger results new ArrayList(nums.length);//2. 双指针for(int i 0; i nums.length; i) {int num nums[i];if(num 0) {return results;}if(i 0 nums[i] nums[i-1]) {continue;}int l i1;int r nums.length-1;while (l r) {int sum num nums[l] nums[r];if(sum 0) {l;} else if(sum 0) {r--;} else {ListInteger integers new ArrayList(3);integers.add(num);integers.add(nums[l]);integers.add(nums[r]);results.add(integers);// 跳过重复的元素while(l r nums[l1] nums[l]) {l;}while (l r nums[r-1] nums[r]) {r--;}l;r--;}}}return results;
}性能
速度超过 99.87 的用户提交还不错。
16. 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。
请你从 nums 中选出三个整数使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1
输入nums [-1,2,1,-4], target 1
输出2
解释与 target 最接近的和是 2 (-1 2 1 2) 。示例 2
输入nums [0,0,0], target 1
输出0提示
3 nums.length 1000
-1000 nums[i] 1000
-10^4 target 10^4
V1-双指针法
思路
针对多个数之和对无序的数组进行一次排序可以大大降低后续的时间复杂度。
我们通过两个指针l r 分别计算每一次的差值找到最小的差异。
当然等于肯定最小直接返回即可。
java 实现 /*** 思路** 能否继续借助排序双指针** 1. 如果相等则直接返回* 2. 否则需要保存最接近的一个值。** 3. 如果差异越来越大则直接停止。** 使用 abs** param nums 数字* param target 目标值* return 结果* since v1*/public int threeSumClosest(int[] nums, int target) {// 最小if(nums.length 3) {return nums[0]nums[1]nums[2];}//1. 排序Arrays.sort(nums);//2. 双指针int diff Integer.MAX_VALUE;for(int i 0; i nums.length; i) {int l i1;int r nums.length-1;// 去重 i,l,rwhile (l r) {// 此处可以直接返回int sum nums[i] nums[l] nums[r];int loopDiff sum-target;if(sum target) {return target;} else if(loopDiff 0) {// 偏小l;if(Math.abs(loopDiff) Math.abs(diff)) {diff loopDiff;}} else {// 偏大r--;if(Math.abs(loopDiff) Math.abs(diff)) {diff loopDiff;}}}}return targetdiff;}效果
Runtime: 5 ms, faster than 99.27% of Java online submissions for Container With Most Water.
Memory Usage: 39 MB, less than 100% of Java online submissions for Container With Most Water.效果还是非常不错的。
V2-优化
思路
针对上面的算法进行优化。
能否继续借助排序双指针 最大值如果依然小于原有差异跳过 最小值如果依然大于原有差异跳过。
直接先把可能有结果的大概范围找到然后再进一步细化快速定位结果。
java 实现 public int threeSumClosest(int[] nums, int target) {// 最小int result nums[0] nums[1] nums[2];//1. 排序Arrays.sort(nums);//2. 双指针for(int i 0; i nums.length-2; i) {int l i1;int r nums.length-1;if (nums[i] nums[i1] nums[i2] - target Math.abs(target - result)) {break; //Too big, cant get better result!}if (i nums.length-3 nums[i1] nums[nums.length-2] nums[nums.length-1] target) {continue; //Too small, skip}while (l r) {// 此处可以直接返回int sum nums[i] nums[l] nums[r];// 如果差异较小if(Math.abs(sum-target) Math.abs(result-target)) {result sum;} else if(sum target) {// 偏小l;} else if(sum target) {r--;} else {return sum;}}}return result;}效果
Runtime: 1 ms, faster than 100.00% of Java online submissions for 3Sum Closest.
Memory Usage: 38.9 MB, less than 85.21% of Java online submissions for 3Sum Closest.18. 4Sum 四数之和
常言道有二有三必须有四。
这道题当然还有四个数之和的版本。
题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target判断 nums 中是否存在四个元素 abc 和 d 使得 a b c d 的值与 target 相等找出所有满足条件且不重复的四元组。
注意
答案中不可以包含重复的四元组。
示例
给定数组 nums [1, 0, -1, 0, -2, 2]和 target 0。满足要求的四元组集合为
[[-1, 0, 0, 1],[-2, -1, 1, 2],[-2, 0, 0, 2]
]解法
解题思路类似上述的 3 个数之和区别是这次我们固定左边 2 个元素。
java 实现如下
public ListListInteger fourSum(int[] nums, int target) {// 大小可以优化ListListInteger resultList new ArrayList(nums.length);//1. 排序Arrays.sort(nums);//2. 类似双指针固定左边2个元素。for(int i 0; i nums.length -3; i) {// 跳过 i 的重复元素if(i 0 nums[i] nums[i-1]) {continue;}for(int j i1; j nums.length-2; j) {// 确保跳过 j 的重复元素if(j i1 nums[j] nums[j-1]) {continue;}// 双指针法则int l j1;int r nums.length-1;while (l r) {int sum nums[i]nums[j]nums[l]nums[r];// 遍历完所有符合的信息if(sum target) {l;} else if(sum target) {r--;} else {ListInteger result Arrays.asList(nums[i], nums[j], nums[l], nums[r]);resultList.add(result);// 跳过重复的元素while (l r nums[l] nums[l1]) {l;}while(l r nums[r] nums[r-1]) {r--;}l;r--;}}}}return resultList;
}经过 3sum 之后你对自己的实现信心十足。
效果对比打败了 49.10% 的用户。WTF!
其实答案也很简单因为大家和你一样已经学会了这种解法。
那么我们还能优化吗
优化方法
思路
主要是可以快速返回的一些优化
1对于长度小于 4 的数组直接返回
2如果在当前循环中 max 小于 target或者 min 大于 target 其实也可以快速跳过。
java 实现
public ListListInteger fourSum(int[] nums, int target) {//1.1 快速返回if(nums.length 4) {return Collections.emptyList();}// 大小可以优化ListListInteger resultList new ArrayList(nums.length);//2. 排序Arrays.sort(nums);//1.2 范围判断final int length nums.length;int min nums[0] nums[1] nums[2] nums[3];int max nums[length-1] nums[length-2] nums[length-3] nums[length-4];if(min target || max target) {return resultList;}//3. 类似双指针固定左边2个元素。for(int i 0; i length -3; i) {// 跳过 i 的重复元素if(i 0 nums[i] nums[i-1]) {continue;}for(int j i1; j length-2; j) {// 确保跳过 j 的重复元素if(j i1 nums[j] nums[j-1]) {continue;}// 双指针法则int l j1;int r length-1;// 快速跳过int minInner nums[i] nums[j] nums[j1] nums[j2];int maxInner nums[i] nums[j] nums[r-1] nums[r];if(minInner target || maxInner target) {continue;}while (l r) {int sum nums[i]nums[j]nums[l]nums[r];// 遍历完所有符合的信息if(sum target) {l;} else if(sum target) {r--;} else {ListInteger result Arrays.asList(nums[i], nums[j], nums[l], nums[r]);resultList.add(result);// 跳过重复的元素while (l r nums[l] nums[l1]) {l;}while(l r nums[r] nums[r-1]) {r--;}l;r--;}}}}return resultList;
}效果
超过了 92.32% 的提交勉强过关。
Runtime: 5 ms, faster than 92.21% of Java online submissions for 4Sum.
Memory Usage: 39.9 MB, less than 56.17% of Java online submissions for 4Sum.ksum
题目
经过了上面的 2sum/3sum/4sum 的洗礼我们现在将这道题做下推广。
如何求 ksum
思路
其实所有的这种解法都可以转换为如下的两个问题
1sum 问题
2将 k sum 问题转换为 k-1 sum 问题
示例代码
/*** 对 k 个数进行求和* param nums 数组* param target 目标值* param k k* param index 下标* return 结果类表* since v1*/
public ListListInteger kSum(int[] nums, int target, int k, int index) {int len nums.length;ListListInteger resultList new ArrayList();if (index len) {return resultList;}if (k 2) {int i index, j len - 1;while (i j) {//find a pairif (target - nums[i] nums[j]) {ListInteger temp new ArrayList();temp.add(nums[i]);temp.add(target - nums[i]);resultList.add(temp);//skip duplicationwhile (i j nums[i] nums[i 1]) {i;}while (i j nums[j - 1] nums[j]) {j--;}i;j--;//move left bound} else if (target - nums[i] nums[j]) {i;//move right bound} else {j--;}}} else {for (int i index; i len - k 1; i) {//use current number to reduce ksum into k-1 sumListListInteger temp kSum(nums, target - nums[i], k - 1, i 1);if (temp ! null) {//add previous resultsfor (ListInteger t : temp) {t.add(0, nums[i]);}resultList.addAll(temp);}while (i len - 1 nums[i] nums[i 1]) {//skip duplicated numbersi;}}}return resultList;
}开源地址
为了便于大家学习所有实现均已开源。欢迎 fork star~ https://github.com/houbb/leetcode 参考资料
https://leetcode-cn.com/problems/two-sum
https://leetcode.com/problems/two-sum/discuss/3/Accepted-Java-O(n)-Solution
https://leetcode-cn.com/problems/3sum
https://leetcode-cn.com/problems/4sum
https://leetcode.com/problems/4sum/discuss/8609/My-solution-generalized-for-kSums-in-JAVA
