本文涉及的基础知识点

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

LeetCode1524. 和为奇数的子数组数目

难度分：1610
给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。
由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
示例 1：
输入：arr = [1,3,5]
输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ，所以答案为 4 。
示例 2 ：
输入：arr = [2,4,6]
输出：0
解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数，所以答案为 0 。
示例 3：
输入：arr = [1,2,3,4,5,6,7]
输出：16
示例 4：
输入：arr = [100,100,99,99]
输出：4
示例 5：
输入：arr = [7]
输出：1
提示：
1 <= arr.length <= 10⁵
1 <= arr[i] <= 100

C++前缀和

令数组长度为n。
空子数组的和为偶数，所以无需枚举空数组。通过左闭右空空间[i,j)枚举所有非空子数组。
i $\in$ [0,n) j $\in$ [i+1,n]
nums[i…j-1]之和就是preSum[j]-preSum[i]
枚举i,cnt0是preSum[i+1…n]偶数元素的数量，cnt1是…奇数元素的数量。
如果preSum[i]是偶数，以nums[i]开始符合条件的子数组数量为cnt1。
如果preSum[i]是奇数，以nums[i]开始符合条件的子数组数量为cnt0。
由于只需要考虑奇偶性，所有nums的元素可以替换成0或1。

代码

核心代码

class Solution {
		public:
			int numOfSubarrays(vector<int>& arr) {
				vector<int> preSum(1);
				for (auto& n : arr) {
					n = n % 2;
					preSum.emplace_back((n + preSum.back()) % 2);
				}
				int cnt0 = (0 == preSum.back()), cnt1 = preSum.back();
				long long ret = 0;
				for (int i = arr.size() - 1; i >= 0; i--) {
					ret +=(preSum[i] ? cnt0 : cnt1);
					cnt0 += (0 == preSum[i]);
					cnt1 += preSum[i];
				}
				return ret % ((int)1e9 + 7);
			}
		};

单元测试

vector<int> arr;
		TEST_METHOD(TestMethod11)
		{
			arr = { 1,3,5 };
			auto res = Solution().numOfSubarrays(arr);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			arr = { 2,4,6 };
			auto res = Solution().numOfSubarrays(arr);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod13)
		{
			arr = { 1,2,3,4,5,6,7 };
			auto res = Solution().numOfSubarrays(arr);
			AssertEx(16, res);
		}
		TEST_METHOD(TestMethod14)
		{
			arr = { 100,100,99,99 };
			auto res = Solution().numOfSubarrays(arr);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod15)
		{
			arr = { 7 };
			auto res = Solution().numOfSubarrays(arr);
			AssertEx(1, res);
		}