连续的子数组和，并拓展为求方案数问题

这是我参与更文挑战的第 2 天，活动详情查看：更文挑战

题目描述

这是 LeetCode 上的 523. 连续的子数组和 ，难度为 中等。

Tag : 「前缀和」

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

• 子数组大小 至少为 2 ，且
• 子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
复制代码

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。
复制代码

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false
复制代码

提示：

• 1 <= nums.length <= $10^5$
• 0 <= nums[i] <= $10^9$
• 0 <= sum(nums[i]) <= $2^{31}$ – 1
• 1 <= k <= $2^{31}$ – 1

基本分析

这是一道很经典的前缀和题目，类似的原题也在蓝桥杯出现过，坐标在 K 倍区间。

本题与那道题不同在于：

• [K 倍区间] 需要求得所有符合条件的区间数量；本题需要判断是否存在。
• [K 倍区间] 序列全是正整数，不需要考虑 $0$ 值问题；本题需要考虑 $0$ 值问题。

数据范围为 $10^4$，因此无论是纯朴素的做法 ($O(n^3)$)还是简单使用前缀和优化的做法 ($O(n^2)$) 都不能满足要求。

我们需要从 $k$ 的倍数作为切入点来做。

预处理前缀和数组 $sum$，方便快速求得某一段区间的和。然后假定 $[i, j]$ 是我们的目标区间，那么有：