本文解决的问题: 按主题归纳 哈希、子串、普通数组 相关高频题型与通用解法。

适用范围: 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
/**
* **进阶**:**时间复杂度小于 O(n2) 的算法解决此问题吗?**
* 1. 使用一个哈希表存储数组元素及其下标。
* 2. 遍历数组,对于每个元素,检查哈希表中是否存在目标值减去当前元素的值。
* 3. 如果存在,返回这两个元素的下标;否则,将当前元素及其下标存入哈希表。
* 4. 如果遍历结束未找到,返回默认值 [0, 0]。
* @param nums 给定一个整数数组
* @param target 整数目标值
* @return 数组下标
*/
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
/**
* 将一组字符串按照字母异位词分组
* 字母异位词指的是字符组成相同,但排列顺序不同的字符串
*
* @param strs 待分组的字符串数组
* @return 分组后的字母异位词列表,每个元素都是一个字符串列表,包含互为字母异位词的字符串
*/
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);
}
// 返回分组后的字母异位词列表,转换为ArrayList以满足返回类型要求
return new ArrayList<>(map.values());
}

/**
由于互为字母异位词的两个字符串包含的字母相同,因此两个字符串中的相同字母出现的次数
一定是相同的,故可以将每个字母出现的次数使用字符串表示,作为哈希表的键。
由于字符串只包含小写字母,因此对于每个字符串,可以使用长度为26的数组
记录每个字母出现的次数。需要注意的是,在使用数组作为哈希表的键时,不同语言的支持程度不同,因此不同语言的实现方式也不同
*/
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']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串,作为哈希表的键
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;
}

子串

和为 K 的子数组

给你一个整数数组 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) {
/*用哈希表的前缀和做法*/
/* 这里相当于利用哈希表存储了当前数之前的前缀和有无等于A-k的,
因为比如说对于[1,1,1],它的前缀和数组为[0,1,2,3],对于索引为2的前缀和
数组处即2(它此时就是A=2的),假设k=1,就是判断[0,1]处有无等于A-k的,这里
是有一个的 */
/* 有点像两数之和,不过那个是在整个哈希表中找k-A的 */
Map<Integer,Integer> map=new HashMap<>();
int count=0;
/* 为什么map key为0赋值为1,比如对于上个例子,前缀和索引为1处此时A-k就等于0
它在map中是已经存在的,此时count要++,故赋值为1 */
map.put(0,1);
int pre_sum=0;
for(int i=0;i<nums.length;++i){
/* 点睛之笔,在当前前缀和之前的map中找 */
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
/**
* 计算滑动窗口中的最大值
* 本方法通过维护前缀和后缀最大值数组来高效计算每个滑动窗口的最大值
* 1. 优先队列算法
* 2. 单调队列算法
* 3. 分块 + 预处理
*
* @param nums 输入的整数数组
* @param k 滑动窗口的大小
* @return 每个滑动窗口的最大值组成的数组
*/
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;

// suffixMax数组用于存储从每个位置开始向后k个元素中的最大值
int[] suffixMax = new int[n];
// prefixMax数组用于存储到每个位置结束向前k个元素中的最大值
int[] prefixMax = new int[n];

// 计算suffixMax数组
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]);
}
}

// 计算prefixMax数组
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]);
}
}

// ans数组用于存储每个滑动窗口的最大值
int[] ans = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
// 每个滑动窗口的最大值是其suffixMax和prefixMax中的较大者
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);
// 当前字符在t中存在,减少计数
if (map[c - 'A'] > 0) {
count--;
}
map[c - 'A']--; // 不论是否在t中,都减少计数(负数表示窗口中的冗余字符)

// 当窗口包含所有t的字符时,尝试收缩左边界
while (count == 0) {
// 更新最小窗口
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minLeft = left;
}

// 左边界右移,恢复字符计数
char leftChar = s.charAt(left);
map[leftChar - 'A']++;
// 如果恢复后该字符的计数大于0,说明移除了一个必需的字符,需增加count
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
/**
* 寻找连续子数组中的最大和
* 本方法实现了一种寻找最大和的高效算法,其核心思想是通过不断累加当前元素并比较累加和,
* 来确定最大子数组的和这种方法被称为Kadane算法
*
* @param nums 这是一个整数数组,其中包含我们要分析的数字
* @return 返回连续子数组的最大和
*/
public int maxSubArray(int[] nums) {
// 初始化最大和为最小整数值,确保任何子数组的和都会比初始值大
int ans = Integer.MIN_VALUE;
// sum用于记录当前子数组的累加和
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()][]);
}

/**
* 如果输入区间为空,返回空数组。
* 按照区间的起始位置对区间进行排序。
* 遍历排序后的区间列表,检查当前区间是否与前一个区间重叠。如果不重叠,则将当前区间加入结果列表;如果重叠,则更新前一个区间的结束位置为两者结束位置的最大值。
* 最后将结果列表转换为二维数组并返回。
* @param intervals 区间列表
* @return
*/
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
/**
* 计算除自身以外所有元素的乘积数组
* 该方法通过两次遍历数组,第一次从左到右,第二次从右到左,来计算每个元素左侧和右侧所有元素的乘积
* 这样做避免了使用除法,可以在不使用额外空间(除结果数组外)的情况下解决问题
*
* @param nums 输入的整数数组
* @return 返回一个数组,其中每个元素为原数组中除自身以外所有元素的乘积
*/
public int[] productExceptSelf(int[] nums) {
// 初始化结果数组,初始值都为1,因为后续操作是乘法,初始值设为1不会影响最终结果
int[] res = new int[nums.length];
Arrays.fill(res, 1);

// 初始化左侧乘积为1,表示第一个元素左边没有元素
int left = 1;
// 初始化右侧乘积为1,表示最后一个元素右边没有元素
int right = 1;

// 从左到右遍历数组,计算每个元素左侧所有元素的乘积
for (int i = 0; i < nums.length; i++) {
// 更新当前元素的值为原值乘以左侧乘积
res[i] = res[i] * left;
// 更新左侧乘积为当前元素的值乘以左侧乘积
left = left * nums[i];
}

// 打印左侧乘积结果,用于调试
//System.out.printf(Arrays.toString(res));

// 从右到左遍历数组,计算每个元素右侧所有元素的乘积
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
/**
* 寻找第一个缺失的正整数
* 该方法旨在找出数组中第一个缺失的正整数,数字从1开始计数
* 通过修改原数组实现,不使用额外空间
*
* @param nums 输入的整数数组
* @return 返回第一个缺失的正整数
*/
public int firstMissingPositive(int[] nums) {
// 遍历数组,将非正整数替换为一个超出数组长度的值
// 这样做是为了忽略非正整数和超出数组长度的值,因为它们不会影响到第一个缺失的正整数
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= 0) {
nums[i] = nums.length + 1;
}
}

// 再次遍历数组,将数组中值为正且不超过数组长度的数对应的位置标记为负数
// 通过将索引对应的值设为负数,来标记这个索引+1(因为数组从0索引开始)的数存在
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]);
}
}

// 最后遍历数组,找到第一个正数,这表示这个位置的索引+1的数缺失
// 如果整个数组都是负数,则说明1到nums.length的数都在数组中,返回nums.length + 1
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return i + 1;
}
}

// 如果数组中所有的数都被标记为负数,说明缺失的第一个正整数是nums.length + 1
return nums.length + 1;
}

数组中的第K个最大元素

【数组】,【分治】、【快速选择】、【排序】、【堆】

给定整数数组 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);
}
}

参考资料