前缀和算法

前缀和，取余，用hash表维护次数，方便统计；

题目描述560

560. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

1
2

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

解答思路

方法一：循环

对每一个以i开头的元素，计算其接下来所有长度的情况，时间复杂度为$O(n^2)$

方法二：前缀和

对于某一个从$i$到$j$连续且和为$k$的数组，相当于从起点加到$j$减去从起点加至$i$的和，使用hash表对上述和出现的数目进行管理即可。其中本题目会用到find函数会使得过程大大简化.

1
2
3
4
5
6
7
8
9
10
11
12

//使用前缀和计算的方法
int subarraySum(Vector<int>& nums, int k){
  unordered_map<int, int> hash;
  hash[0] = 1;
  int tmp = 0, cnt = 0;
  for (auto x: nums){
    tmp += x;
    if(hash.find(tmp - x) != hash.end()) cnt += hash[tmp - x];//a
    hash[tmp]++;//b
  }
  return cnt;
}

总结

这道题最大的问题在于思路：将枚举的方法转换为遍历求和后求差值，并用hash表对次数进行管理；

关于代码实现：实现对hash\vector等数据结构使用find函数时，若未查到，则会返回end()的值；

深入思考，a和b两行代码能够对调？显然是不能的，考虑极端情况，k=0时若对调会导致得到的结果相对正确答案偏大，故无法对调。（计算机很考边界条件啊！！！）

题目描述974

974.和可被 K 整除的子数组

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例：

1
2
3
4
5

输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

提示：

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

解答思路

使用前缀和算法，考虑每个位置sum的余数，余数为0自然可以整除，除此外，对于前方余数相同的指标个数，即可表示为子数组数；

注意，针对负数的取余具有特殊性；

1
2
3
4
5
6
7
8
9
10
11
12

int subarrayDivByk(vector<int>& A, int K){
  unordered_map<int,int> cnt;//用hash表管理余数出现的次数
  int ans = 0, sum = 0;
  for (int i = 0; i < A.size(); ++i){
    sum += A[i];
    int tmp = (sum%K + K)%K;
    if(tmp == 0) ans++;
    ans += cnt[tmp];
    cnt[tmp]++;
  }
  return ans;
}

• ← Previous Post
• Next Post →