前缀和
前缀和是一种数组变换方法，通过将数组中每个元素替换为从数组起始位置到当前位置的所有元素之和。这样，计算任意区间的和变得非常高效，只需一次前缀和计算即可，而不需要多次重复计算。
1
2
3
| int[] nums;
int n = nums.length, sum[] = new int[n+1];
sum[i+1] = sum[i] + nums[i];
|
需要用sum[0]表示空数组的和
l到r的区间和表示为 sum[r+1] - sum[l]
例如，nums[0]到nums[5]的区间和表示为 sum[6] - sum[0]
二维前缀和
定义sum[i+1][j+1]表示左上角grid[0][0]，右下角grid[i][j]的子矩阵元素和
1
2
3
4
5
6
| int[][] sum = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + grid[i][j];
}
}
|
通过二维前缀和获取任意子矩阵元素和，设要获取的子矩阵的左上角为grid[l][u]，右下角为grid[r-1][d-1]
1
| res = sum[r][d] - sum[l][d] - sum[r][u] + sum[l][u]
|
前缀和+哈希表
用于求解区间和的出现次数问题
O(n)级别
在遍历前缀和的过程中，把前缀和的当前值加入哈希表，后续便可以直接索引到需要的区间和的出现次数。
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
1
2
| 输入：nums = [1,1,1], k = 2
输出：2
|
示例 2：
1
2
| 输入：nums = [1,2,3], k = 3
输出：2
|
提示：
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
前缀和+哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length, res = 0, sum[] = new int[n+1];
for (int i = 0; i < n; i++) {
sum[i+1] = sum[i] + nums[i];
}
Map<Integer, Integer> map = new HashMap<>();
for (int s : sum) {
res += map.getOrDefault(s - k, 0);
map.put(s, map.getOrDefault(s, 0) + 1);
}
return res;
}
}
|
给你一个下标从 0 开始的整数数组 nums ，以及整数 modulo 和整数 k 。
请你找出并统计数组中 趣味子数组 的数目。
如果 子数组 nums[l..r] 满足下述条件，则称其为 趣味子数组 ：
- 在范围
[l, r] 内，设 cnt 为满足 nums[i] % modulo == k 的索引 i 的数量。并且 cnt % modulo == k 。
以整数形式表示并返回趣味子数组的数目。
**注意：**子数组是数组中的一个连续非空的元素序列。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 输入：nums = [3,2,4], modulo = 2, k = 1
输出：3
解释：在这个示例中，趣味子数组分别是：
子数组 nums[0..0] ，也就是 [3] 。
- 在范围 [0, 0] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..1] ，也就是 [3,2] 。
- 在范围 [0, 1] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
子数组 nums[0..2] ，也就是 [3,2,4] 。
- 在范围 [0, 2] 内，只存在 1 个下标 i = 0 满足 nums[i] % modulo == k 。
- 因此 cnt = 1 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组。因此，答案为 3 。
|
示例 2：
1
2
3
4
5
6
7
8
9
10
| 输入：nums = [3,1,9,6], modulo = 3, k = 0
输出：2
解释：在这个示例中，趣味子数组分别是：
子数组 nums[0..3] ，也就是 [3,1,9,6] 。
- 在范围 [0, 3] 内，只存在 3 个下标 i = 0, 2, 3 满足 nums[i] % modulo == k 。
- 因此 cnt = 3 ，且 cnt % modulo == k 。
子数组 nums[1..1] ，也就是 [1] 。
- 在范围 [1, 1] 内，不存在下标满足 nums[i] % modulo == k 。
- 因此 cnt = 0 ，且 cnt % modulo == k 。
可以证明不存在其他趣味子数组，因此答案为 2 。
|
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^91 <= modulo <= 10^90 <= k < modulo
问题转换+前缀和+哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
int n = nums.size(), sum[] = new int[n+1];
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < n; i++) {
sum[i+1] = (sum[i] + (nums.get(i) % modulo == k ? 1 : 0)) % modulo;
}
long res = 0;
cnt.put(0, 1);
for (int i = 0; i < n; i++) {
res += cnt.getOrDefault((sum[i+1]-k+modulo) % modulo, 0);
cnt.put(sum[i+1], cnt.getOrDefault(sum[i+1], 0) + 1);
}
return res;
}
}
|
给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件，则称其为 美丽字符串 ：
vowels == consonants，即元音字母和辅音字母的数量相等。(vowels * consonants) % k == 0，即元音字母和辅音字母的数量的乘积能被 k 整除。
返回字符串 s 中 非空美丽子字符串 的数量。
子字符串是字符串中的一个连续字符序列。
英语中的 元音字母 为 'a'、'e'、'i'、'o' 和 'u' 。
英语中的 辅音字母 为除了元音字母之外的所有字母。
示例 1：
1
2
3
4
5
6
7
8
| 输入：s = "baeyh", k = 2
输出：2
解释：字符串 s 中有 2 个美丽子字符串。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["y","h"]）。
可以看出字符串 "aeyh" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["b","y"]）。
可以看出字符串 "baey" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。
|
示例 2：
1
2
3
4
5
6
7
| 输入：s = "abba", k = 1
输出：3
解释：字符串 s 中有 3 个美丽子字符串。
- 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "abba"，vowels = 2（["a","a"]），consonants = 2（["b","b"]）。
可以证明字符串 s 中只有 3 个美丽子字符串。
|
示例 3：
1
2
3
| 输入：s = "bcdf", k = 1
输出：0
解释：字符串 s 中没有美丽子字符串。
|
提示：
1 <= s.length <= 5 * 10^41 <= k <= 1000s 仅由小写英文字母组成。
前缀和+哈希嵌套哈希
这题是一道很典的题，即把元音字母视为+1, 非元音字母视为-1
这样 vowels==consonants，既可以转化为前缀和Hash模型
但这题还有一个条件(vowels∗consonants)%k==0，所以哈希里面还需要嵌套一个哈希
设子字符串的长度为len
则第一个条件vowels==consonants说明，vowels和consonants的长度都为len/2
考虑第二个条件(vowels * consonants) % k == 0
(len/2)^2 % k == 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
| class Solution {
boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
public long beautifulSubstrings(String s, int k) {
char[] str = s.toCharArray();
int n = str.length;
int offset = 0;
for (int i = 1; i <= k; i++) {
if ((i * i) % k == 0) {
offset = i * 2;
break;
}
}
long res = 0;
Map<Integer, Map<Integer, Integer>> hash = new HashMap<>();
hash.put(0, new HashMap<>());
hash.get(0).put(0, 1);
int acc = 0;
for (int i = 0; i < n; i++) {
if (isVowel(str[i])) acc++;
else acc--;
int key = (i + 1) % offset;
if (hash.containsKey(acc)) {
var hash2 = hash.get(acc);
res += hash2.getOrDefault(key, 0);
}
hash.computeIfAbsent(acc, x -> new HashMap<>()).merge(key, 1, Integer::sum);
}
return res;
}
}
|
更多题目
