本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

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

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。
示例 1：
输入：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]
示例 2:
输入: nums = [5], k = 9
输出: 0
提示:
1 <= nums.length <= 3 * 10⁴
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴

前缀和

通过左闭右开空间[i,j)枚举非空子数组。
i$\in$[0,n)
j $\in$[i+1,n]
cnt[k1] 记录preSum[i+1…n]中%k == k1的数量。
k2= preSum[i] %k , 以nums[i]开头符合条件的子数组数量为：cnt[k2]。
累加之，就是答案。

代码

打开打包代码的方法兼述单元测试

核心代码

class Solution {
		public:
			int subarraysDivByK(vector<int>& nums, int k) {
				vector<long long> preSum(1);
				for (const auto& n : nums) {
					preSum.emplace_back(n + preSum.back());
				}
				vector<int> cnt(k);
				cnt[Modk(preSum.back(), k)]++;
				long long ret = 0;
				for (int i = nums.size() - 1; i >= 0; i--) {
					const int iMod = Modk(preSum[i],k);
					ret += cnt[iMod];
					cnt[iMod]++;
				}
				return ret;
			}
			int Modk(const long long& ll, const int& k) {
				return ((ll % k) + k) % k;
			}
		};		

单元测试

vector<int> nums;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 4, 5, 0, -2, -3, 1 }, k = 5;
			auto res = Solution().subarraysDivByK(nums, k);
			AssertEx(7, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 5}, k = 9;
			auto res = Solution().subarraysDivByK(nums, k);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { -2 }, k = 6;
			auto res = Solution().subarraysDivByK(nums, k);
			AssertEx(0, res);
		}