本文解决的问题: 按主题归纳 哈希、子串、普通数组 相关高频题型与通用解法。
适用范围: LeetCode 中文站题目,示例主要使用 Java。
阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。
哈希
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 *target* 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
提示:
2 <= nums.length <= 104
109 <= nums[i] <= 109
109 <= target <= 109
只会存在一个有效答案
示例:
1 2 3 4 5 6 7
| 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1]
输入:nums = [3,2,4], target = 6 输出:[1,2] 解释:因为 nums[1] + nums[2] == 6 , 返回[1, 2]
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int num = nums[i]; if (map.containsKey(target - num)) { return new int[] {map.get(target - num), i}; } map.put(num, i); } return new int[] {0,0}; }
|
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
提示:
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
提示:
1 2 3 4 5 6 7 8
| 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
输入: strs = [""] 输出: [[""]]
输入: strs = ["a"] 输出: [["a"]]
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
|
public List<List<String>> groupAnagrams(String[] strs) { Map<Integer, List<String>> map = new HashMap<>(); for (String str : strs) { char[] chars = str.toCharArray(); Arrays.sort(chars); int key = new String(chars).hashCode(); List<String> orDefault = map.getOrDefault(key, new ArrayList<>()); if (orDefault.isEmpty()) { map.put(key, orDefault); } orDefault.add(str); } return new ArrayList<>(map.values()); }
public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<String, List<String>>(); for (String str : strs) { int[] counts = new int[26]; int length = str.length(); for (int i = 0; i < length; i++) { counts[str.charAt(i) - 'a']++; } StringBuffer sb = new StringBuffer(); for (int i = 0; i < 26; i++) { if (counts[i] != 0) { sb.append((char) ('a' + i)); sb.append(counts[i]); } } String key = sb.toString(); List<String> list = map.getOrDefault(key, new ArrayList<String>()); list.add(str); map.put(key, list); } return new ArrayList<List<String>>(map.values()); }
|
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
提示:
0 <= nums.length <= 105
109 <= nums[i] <= 109
示例:
1 2 3 4 5 6 7 8 9
| 输入:nums = [100,4,200,1,3,2] 输出:4 解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
输入:nums = [0,3,7,2,5,8,4,6,0,1] 输出:9
输入:nums = [1,0,1,2] 输出:3
|
代码:
1 2 3 4 5 6 7 8 9 10 11
| public int longestConsecutive(int[] nums) { Arrays.sort(nums); Map<Integer, Integer> map = new HashMap<>(); int r = 0; for (int num : nums) { int i1 = map.getOrDefault(num - 1, 0) + 1; r = Math.max(r, i1); map.put(num, i1); } return r; }
|
给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 。
如果小数部分为循环小数,则将循环的部分括在括号内。
如果存在多个答案,只需返回 任意一个 。
对于所有给定的输入,保证 答案字符串的长度小于 104 。
提示:
-231 <= numerator, denominator <= 231 - 1
denominator != 0
示例:
1 2 3 4 5 6 7 8 9 10 11
| 示例 1: 输入:numerator = 1, denominator = 2 输出:"0.5"
示例 2: 输入:numerator = 2, denominator = 1 输出:"2"
示例 3: 输入:numerator = 4, denominator = 333 输出:"0.(012)"
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| public String fractionToDecimal(int numerator, int denominator) { long numeratorLong = numerator; long denominatorLong = denominator; if (numeratorLong % denominatorLong == 0) { return String.valueOf(numeratorLong / denominatorLong); }
StringBuffer sb = new StringBuffer(); if (numeratorLong < 0 ^ denominatorLong < 0) { sb.append('-'); }
numeratorLong = Math.abs(numeratorLong); denominatorLong = Math.abs(denominatorLong); long integerPart = numeratorLong / denominatorLong; sb.append(integerPart); sb.append('.');
StringBuffer fractionPart = new StringBuffer(); Map<Long, Integer> remainderIndexMap = new HashMap<Long, Integer>(); long remainder = numeratorLong % denominatorLong; int index = 0; while (remainder != 0 && !remainderIndexMap.containsKey(remainder)) { remainderIndexMap.put(remainder, index); remainder *= 10; fractionPart.append(remainder / denominatorLong); remainder %= denominatorLong; index++; } if (remainder != 0) { int insertIndex = remainderIndexMap.get(remainder); fractionPart.insert(insertIndex, '('); fractionPart.append(')'); } sb.append(fractionPart.toString());
return sb.toString(); }
|
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
**注意:**答案中不可以包含重复的三元组。
提示:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| 示例 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 。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int target = -nums[i]; int left = i + 1, right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { list.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right - 1] == nums[right]) { right--; } left++; right--; } else if (target < sum) { right--; } else { left++; } } } return list; }
|
子串
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 *该数组中和为 k ***的子数组的个数 。
子数组是数组中元素的连续非空序列。
提示:
1 <= nums.length <= 2 * 104
1000 <= nums[i] <= 1000
107 <= k <= 107
示例:
1 2 3 4 5
| 输入:nums = [1,1,1], k = 2 输出:2
输入:nums = [1,2,3], k = 3 输出:2
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map=new HashMap<>(); int count=0;
map.put(0,1); int pre_sum=0; for(int i=0;i<nums.length;++i){ pre_sum+=nums[i]; if(map.containsKey(pre_sum-k)){ count+=map.get(pre_sum-k); } map.put(pre_sum,map.getOrDefault(pre_sum,0)+1); } return count; }
|
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到滑动窗口内的 k 个数字,滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
提示:
1 <= nums.length <= 105
104 <= nums[i] <= 104
1 <= k <= nums.length
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 输入:nums = [1], k = 1 输出:[1]
|
代码:
解法说明
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
|
public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] suffixMax = new int[n]; int[] prefixMax = new int[n]; for (int i = 0; i < n; i++) { if (i % k == 0) { suffixMax[i] = nums[i]; } else { suffixMax[i] = Math.max(suffixMax[i - 1], nums[i]); } } for (int i = n - 1; i >= 0; i--) { if (i == n - 1 || (i + k) % k == 0) { prefixMax[i] = nums[i]; } else { prefixMax[i] = Math.max(prefixMax[i + 1], nums[i]); } } int[] ans = new int[n - k + 1]; for (int i = 0; i < n - k + 1; i++) { ans[i] = Math.max(suffixMax[i + k - 1], prefixMax[i]); } return ans; }
|
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
**进阶:**你能设计一个在 o(m+n) 时间内解决此问题的算法吗?
注意:
- 对于
t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果
s 中存在这样的子串,我们保证它是唯一的答案。
提示:
m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成
示例:
1 2 3 4 5 6 7 8 9 10 11 12
| 输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
输入:s = "a", t = "a" 输出:"a" 解释:整个字符串 s 是最小覆盖子串。
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中, 因此没有符合条件的子字符串,返回空字符串。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| public String minWindow(String s, String t) {
int[] map = new int[58]; for (char c : t.toCharArray()) { map[c - 'A']++; } int left = 0, right = 0; int minLen = Integer.MAX_VALUE; int minLeft = 0; int count = t.length();
while (right < s.length()) { char c = s.charAt(right); if (map[c - 'A'] > 0) { count--; } map[c - 'A']--;
while (count == 0) { if (right - left + 1 < minLen) { minLen = right - left + 1; minLeft = left; }
char leftChar = s.charAt(left); map[leftChar - 'A']++; if (map[leftChar - 'A'] > 0) { count++; } left++; } right++; }
return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen); }
|
普通数组
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组是数组中的一个连续部分。
**进阶:**如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。
提示:
1 <= nums.length <= 105
104 <= nums[i] <= 104
示例:
1 2 3 4 5 6 7 8 9
| 输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
输入:nums = [1] 输出:1
输入:nums = [5,4,-1,7,8] 输出:23
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
public int maxSubArray(int[] nums) { int ans = Integer.MIN_VALUE; int sum = 0; for (int num : nums) { if (sum <= 0) { sum = num; } else { sum += num; } ans = Math.max(ans, sum); } return ans; }
|
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
提示:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
示例:
1 2 3 4 5 6 7
| 输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| public int[][] merge(int[][] intervals) { List<int[]> list = new ArrayList<>(); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); pq.addAll(Arrays.asList(intervals)); while (!pq.isEmpty()) { int[] cur = pq.poll(); int[] res = new int[2]; res[0] = cur[0]; res[1] = cur[1]; list.add(res); while (!pq.isEmpty()) { int[] peek = pq.peek(); if (cur[1] >= peek[0] || res[1] >= peek[0]) { res[0] = Math.min(peek[0], res[0]); res[1] = Math.max(pq.poll()[1], res[1]); } else { break; } } }
return list.toArray(new int[list.size()][]); }
public int[][] merge(int[][] intervals) { if (intervals.length == 0) { return new int[0][2]; } Arrays.sort(intervals, new Comparator<int[]>() { public int compare(int[] interval1, int[] interval2) { return interval1[0] - interval2[0]; } }); List<int[]> merged = new ArrayList<int[]>(); for (int i = 0; i < intervals.length; ++i) { int L = intervals[i][0], R = intervals[i][1]; if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) { merged.add(new int[]{L, R}); } else { merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R); } } return merged.toArray(new int[merged.size()][]); }
|
给定一个整数数组 nums,将数组中的元素向右轮转 k **个位置,其中 k **是非负数。
- 尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为
O(1) 的 原地 算法解决这个问题吗?
提示:
1 <= nums.length <= 105
231 <= nums[i] <= 231 - 1
0 <= k <= 105
示例:
1 2 3 4 5 6 7 8 9 10 11 12
| 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]
输入:nums = [-1,-100,3,99], k = 2 输出:[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| public void rotate(int[] nums, int k) { k %=nums.length; reverse(nums, 0, nums.length - 1); reverse(nums, 0, k - 1); reverse(nums, k, nums.length - 1); }
public void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start += 1; end -= 1; } }
|
【数组】、【前缀和】
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法,**且在 O(n) 时间复杂度内完成此题。
**进阶:**你可以在 O(1) 的额外空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组 不被视为 额外空间。)
提示:
2 <= nums.length <= 105
30 <= nums[i] <= 30
输入 保证 数组 answer[i] 在 32 位 整数范围内
示例:
1 2 3 4 5
| 输入: nums = [1,2,3,4] 输出: [24,12,8,6]
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
public int[] productExceptSelf(int[] nums) { int[] res = new int[nums.length]; Arrays.fill(res, 1); int left = 1; int right = 1; for (int i = 0; i < nums.length; i++) { res[i] = res[i] * left; left = left * nums[i]; } for (int i = nums.length - 1; i >= 0; i--) { res[i] = res[i] * right; right = right * nums[i]; } return res; }
|
【数组】,【哈希】
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。
提示:
1 <= nums.length <= 105
231 <= nums[i] <= 231 - 1
示例:
1 2 3 4 5 6 7 8 9 10 11
| 输入:nums = [1,2,0] 输出:3 解释:范围 [1,2] 中的数字都在数组中。
输入:nums = [3,4,-1,1] 输出:2 解释:1 在数组中,但 2 没有。
输入:nums = [7,8,9,11,12] 输出:1 解释:最小的正数 1 没有出现。
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
public int firstMissingPositive(int[] nums) { for (int i = 0; i < nums.length; i++) { if (nums[i] <= 0) { nums[i] = nums.length + 1; } } for (int i = 0; i < nums.length; i++) { int num = Math.abs(nums[i]); if (num <= nums.length) { nums[num - 1] = -Math.abs(nums[num - 1]); } } for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { return i + 1; } } return nums.length + 1; }
|
【数组】,【分治】、【快速选择】、【排序】、【堆】
给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
提示:
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
示例:
1 2 3 4 5
| 输入: [3,2,1,5,6,4], k = 2 输出: 5
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
|
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| class Solution { int quickselect(int[] nums, int l, int r, int k) { if (l == r) { return nums[k]; } int x = nums[l], i = l - 1, j = r + 1; while (i < j) { do { i++; } while (nums[i] < x); do { j--; } while (nums[j] > x); if (i < j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } if (k <= j) { return quickselect(nums, l, j, k); } return quickselect(nums, j + 1, r, k); }
public int findKthLargest(int[] _nums, int k) { int n = _nums.length; return quickselect(_nums, 0, n - 1, n - k); } }
|
参考资料