0523. Continuous Subarray Sum ============================= 题目信息 -------- :题号: 0523 :难度: Medium :主题: 连续子数组、长度下限、整倍数、布尔判定 :原题: `LeetCode 0523 `_ :重点: 子数组必须连续且长度至少为 2、元素和应是 k 的整数倍、零也是 k 的倍数 题目重述 -------- 给定非负整数数组 ``nums`` 和正整数 ``k``,判断是否存在一个长度至少为 ``2`` 的连续子数组,使该子数组的元素和等于 ``k`` 的某个整数倍。 整数倍可以是 ``0``,因此和为 ``0`` 的合格子数组也满足条件。只需返回是否存在,不需要返回子数组位置;单个元素即使本身是 ``k`` 的倍数,也不满足长度要求。 自建示例 -------- 前两个元素组成整倍数: .. code-block:: text 输入:nums = [4,2,3],k = 3 输出:true 解释:连续子数组 [4,2] 的和为 6,是 3 的 2 倍,且长度为 2。 不存在合格连续区间: .. code-block:: text 输入:nums = [1,2,3],k = 7 输出:false 解释:长度至少为 2 的连续子数组和为 3、5 或 6,都不是 7 的整数倍。 相同前缀余数之间形成整倍数 -------------------------- 若两个前缀和对 ``k`` 取模后相同,它们的差值就是 ``k`` 的整数倍;差值对应的数组区间必须至少包含两个元素。对每个余数只记录最早出现的位置,后面再次出现时得到的区间最长,也最容易满足长度要求。 初始余数 0 放在位置 ``-1``,覆盖从数组开头开始的区间;题目中的 ``k`` 为正数,余数始终在 ``0..k-1``。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool checkSubarraySum(std::vector& nums, int k) { std::unordered_map first; first[0] = -1; long long prefix = 0; for (int i = 0; i < static_cast(nums.size()); ++i) { prefix = (prefix + nums[i]) % k; int remainder = static_cast(prefix); auto it = first.find(remainder); if (it != first.end()) { if (i - it->second >= 2) return true; } else { first[remainder] = i; } } return false; } }; 代码分析 -------- 前缀余数相等与区间和为 ``k`` 的倍数等价,保留最早位置不会丢失任何长度至少 2 的可行区间。每个元素只做一次哈希查找,平均时间复杂度为 ``O(n)``,额外空间复杂度为 ``O(min(n,k))``。