题目

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

示例：

输入：nums = [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]

输入: nums = [5], k = 9
输出: 0

解答 & 代码

用哈希表存储**<前缀和 % k, 出现次数>**

注意这里存储的是 前缀和 % k，而不是前缀和，因为本题求的是和可被 k 整除的子数组，根据同余定理，如果前缀和 preSum1 % k == preSum2 % k，那么 (preSum2 - preSum1) % k == 0。因此只需存储前缀和 % k，同时还能防止求和溢出，并减小哈希表的空间复杂度到 O(k)

这里还需要注意和为负数的情况，为了防止取模为负数，因此令 **sum = (sum % k + k) % k**

class Solution {
public:
  int subarraysDivByK(vector<int>& nums, int k) {
      int result = 0;

      // 哈希表存储 <前缀和 % k, 出现次数>
      unordered_map<int, int> sumCntMap;
      sumCntMap[0] = 1;    // 初始存入 <0, 1>
      int sum = 0;        // 前缀和
      for(int i = 0; i < nums.size(); ++i)
      {
          sum += nums[i];
          sum = (sum % k + k) % k;    // 这种写法，为了防止前缀和为负数导致取模为负数的情况
          // 根据同余定理，如果 preSum1 % k == preSum2 % k，那么 (preSum2 - preSum1) % k == 0
          // 因此，和可被 k 整除的子数组加上 sumCntMap[sum]
          result += sumCntMap[sum];
          sumCntMap[sum] += 1;        // 计数 +1
      }
      return result;
  }
};

复杂度分析：设 nums 数组长为 n，求被 k 整除的子数组个数

时间复杂度 O(n)：
空间复杂度 O(min(n, k))：

执行结果：

执行结果：通过

执行用时：56 ms, 在所有 C++ 提交中击败了 33.52% 的用户
内存消耗：30.8 MB, 在所有 C++ 提交中击败了 80.52% 的用户

hot 100

[中等] 974. 和可被 K 整除的子数组

题目

解答 & 代码