基础算法 - 前缀和
前缀和（Prefix Sum）是一种常见且高效的算法技巧，广泛应用于一系列数据处理和查询问题中。通过预处理数组，前缀和能够显著降低区间和查询的时间复杂度，是解决许多连续区间问题的重要工具。
前缀和的主要特点包括：
- 预处理数组：通过一次遍历计算出前缀和数组，使得后续的区间和查询能够在常数时间内完成。
- 高效查询：在计算了前缀和数组后，可以在O(1)时间复杂度内计算任意区间的和。
前缀和通常用于解决一系列需要频繁查询区间和的问题，如区间和查询、动态数组处理等。
相关题目
难度：中等
最优解：前缀和+哈希表
前缀和：将子数组解释为 ai+1 + ai+2 + …. + aj = (a0 + a1 + …. + aj ) - (a0 + a1 + …. + ai ) = prej - prei
如果要想知道是否存在这样的子数组满足和为k，只需要寻找 prei = prej - k
每一步记录以下pre就可以，要使用哈希表的方法记录。。。
体会哈希表的用法，因为我们需要知道某一个前缀和出现过没有，出现了几次，这使得哈希表可以完美地进行记录。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
int pre = 0;
int count = 0;
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
int need = pre - k;
count += map.getOrDefault(need, 0);
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return count;
}
}
|
难度：中等
同样使用前缀和+哈希表的方法解决。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int numberOfSubarrays(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int count = 0;
int pre = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]%2==1){
pre+=1;
}
int need = pre-k;
count += map.getOrDefault(need,0);
map.put(pre,map.getOrDefault(pre,0)+1);
}
return count;
}
}
|
哈希表可以用数组代替：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int len = nums.length;
int res = 0;
int oddCount = 0;
int[] prefix = new int[len + 1];
prefix[0] = 1;
for (int num : nums) {
if (num % 2 == 1) {
oddCount++;
}
if (oddCount >= k) {
res += prefix[oddCount - k];
}
prefix[oddCount]++;
}
return res;
}
}
|
难度：中等
前缀和变体。
前面是要求子数组的和为k，prei - prej = k
此题是要求子数组是k的整数倍, prei - prej = n*k ，这就要求两个前缀和同余，故我们只需要计算当前前缀和对k的余数，并在已经记录的前缀和的余数中找是否有相同的，如果有，那么就算满足要求的子数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int subarraysDivByK(int[] nums, int k) {
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int pre = 0;
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
int rem = ((pre % k) + k) % k;
count += map.getOrDefault(rem, 0);
map.put(rem, map.getOrDefault(rem, 0) + 1);
}
return count;
}
}
|
同理哈希表也可以用数组代替，可以提高运行时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int subarraysDivByK(int[] nums, int k) {
int[] remainders = new int[k];
remainders[0] = 1;
int sum = 0;
int res = 0;
for(int num:nums){
sum+=num;
int rem = ((sum%k)+k) % k;
res += remainders[rem];
remainders[rem]++;
}
return res;
}
}
|
难度：中等
该题比上一题多了一个限制，子数组的长度至少为2，并且该题是如果找到合适的子数组就可以直接返回布尔值。
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
| import java.util.HashSet;
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int len = nums.length;
if (len < 2) return false;
int sum_fast = nums[0] + nums[1];
if (sum_fast % k == 0) return true;
HashSet<Integer> set = new HashSet<>();
set.add(0);
int sum_slow = 0;
for (int i = 2; i < len; i++) {
sum_fast += nums[i];
sum_slow += nums[i - 2];
int rem = ((sum_slow % k) + k) % k;
if (!set.contains(rem)) {
set.add(rem);
}
int targetRem = ((sum_fast % k) + k) % k;
if (set.contains(targetRem)) return true;
}
return false;
}
}
|
同样也可以用数组，不用哈希表。
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
| class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int len = nums.length;
if(len<2)return false;
int sum_fast = 0;
int sum_slow = 0;
sum_fast = nums[0]+nums[1];
if(sum_fast%k==0) return true;
int[] rems = new int[k];
rems[0] = 1;
for(int i=2;i<len;i++){
sum_fast += nums[i];
sum_slow += nums[i-2];
int rem = ((sum_slow % k)+k) %k;
rems[rem]++;
int targetRem = ((sum_fast %k)+k) % k;
if(rems[targetRem]!=0) return true;
}
return false;
}
}
|
这样按理说是没问题的….可是题目中有一个示例k=Integer.MAX_VALUE给内存干超了。。。。
但确实，在k值比较大的情况，使用数组会导致空间的浪费，还是应该使用HashSet。
