P4202. 数字游戏

解题思路

前缀和

本题需要用到前缀和的概念。

对于一个给定的数列 A，它的前缀和数列 S 中 S[i+1] 表示从第 1 个元素到第 i 个元素的总和。

假设 nums 是一个 int 型列表，形如 sum(nums[0:i+1]) 就是从索引 0 对应的元素开始，累加到索引 i 对应的元素的前缀和。

例如 nums = [1, 2, 3, 4]，那么其前缀和列表即为 pre_sum_lst = [0, 1, 3, 6, 10]。

前缀和的作用是可以在 O(1) 的时间复杂度下快速地计算出某段连续子数组的和。即：

例如对于上述 nums = [1, 2, 3, 4] 而言，如果想快速计算出子数组 nums[1:4] = [2, 3, 4] 的结果，只需要计算 pre_sum_lst[4] - pre_sum_lst[1] = 10 - 1 = 9 即为答案。

前缀和的作用也可以解释，为什么我们会把 0 也视为一个前缀和并且放在前缀和列表的第一个位置。由于设置了 pre_sum_lst[0] = 0，那么 pre_sum_lst[i] - pre_sum_lst[0] = sum(nums[:i])，才能够得到起始位置为原数组 nums 中第一个元素的连续子数组的和。

简单的数学推导

假设连续子数组 nums[i:j] 的和为 A，由上述关于前缀和的定义可知：

假设 A 是符合题意的连续子数组和（此时应该输出 1 作为结果），那么存在：

成立，即：

成立。打开括号并移项，可以得到：

成立。

因此，我们只需要找到两个前缀和 pre_sum_lst[i] 和 pre_sum_lst[j]，能够满足上述式子，就可以说明存在符合题意的连续子数组了。

哈希集合的使用

在本题中，只需要判断能否找到一个满足题意的连续子数组，显然下标的具体值并不重要。故我们可以直接使用一个哈希集合 pre_sum_set 来储存所有的前缀和对 m 求余的结果，而不用考虑下标。

我们可以在一个循环中对前缀和进行计算和判断，其具体流程如下：

1. 计算包含了 i 位置元素的前缀和 pre_sum 2. 计算当前前缀和对 m 的求余结果 pre_sum % m 3. 判断求余结果 pre_sum % m 是否位于哈希集合中，若：

• 存在，则说明在此之前存在某个前缀和对 m 求余可以得到一样的结果。退出循环，输出 1
• 不存在，继续循环

4. 如果在上一步中没有退出循环，则将 pre_sum % m 存入哈希集合 pre_sum_set 中

将该核心逻辑转化为代码即为：

扩展思考

如果本题不仅要判断能否找到符合要求的连续子数组，还对题目做如下修改：

• 输出所有符合要求的子数组的起始坐标和结束坐标
• 输出符合要求的最长子数组的长度
• 输出符合要求的最短子数组的长度
• 输出所有符合要求的子数组的数目

那么代码逻辑应该如何修改？

其中，第四种问法等价于 经典题型. 可被 K 整除的子数组。

边界与注意事项

• 集合 pre_sum_set 预先放入了 0：它代表「空前缀」对 m 的余数。这样当从第一张牌开始的某段前缀和本身对 m 取余为 0 时，也能在集合中查到 0 而正确命中，不会漏掉「子数组从头开始」这种情况。
• 代码是「先查询、后插入」：每轮先判断当前 pre_sum % m 是否已在集合中，命中才把 isFind 置为 True；没命中才把它插入集合。这保证匹配到的两个前缀一定来自不同位置，对应的连续子数组至少包含一张牌，不会出现长度为 0 的假匹配。
• 只有一张牌满足条件的情况同样被覆盖：某张牌加入后的前缀余数若与它加入前的前缀余数相同，就意味着这张牌单独构成的子数组和对 m 取余为 0，会在当轮直接命中。
• 找到答案立即 break，后面的牌不再处理；若遍历完 n 张牌都没有命中，isFind 保持 False。最终输出用 int(isFind)（C++ 版为条件表达式）把布尔值转成数字 0 或 1，符合题目的输出格式要求。