尧图网站建设 
LeetCode 523Continuous Subarray Sum —— Go 实现前缀和与同余定理判定 k 倍数子数组【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 leetcode/0523.Continuous-Subarray-Sum/README.md 的题解展开系统讲解LeetCode 523. Continuous Subarray Sum的完整解法如何用前缀和 同余定理 哈希表在 O(n) 时间内判断数组中是否存在长度至少为 2、且元素和为 k 的倍数的连续子数组。读完本文你将掌握该类「子数组和与 k 整除」问题的通用套路余数映射并能直接复用本仓库中可编译、可测试的 Go 实现。题目描述给定一个整数数组nums和一个整数k判断nums是否存在一个大小至少为 2的连续子数组其元素之和是k的倍数。若存在返回true否则返回false。关于倍数的定义整数x是k的倍数当且仅当存在整数n使得x n * k。特别地0永远是k的倍数——这一点在 k 恰好等于某个子段和时非常关键。示例示例 1输入: nums [23,2,4,6,7], k 6 输出: true 解释: [2, 4] 是一个长度为 2 的连续子数组其元素和为 6是 6 的倍数。示例 2输入: nums [23,2,6,4,7], k 6 输出: true 解释: [23, 2, 6, 4, 7] 是长度为 5 的连续子数组其元素和为 42 7 * 6是 6 的倍数。示例 3输入: nums [23,2,6,4,7], k 13 输出: false数据约束约束项取值范围对解法的影响nums.length1 nums.length 10^5需要 O(n) 或更优的算法O(n²) 会超时nums[i]0 nums[i] 10^9前缀和单调不减无负数干扰sum(nums[i])0 sum 2^31 - 1单次前缀和不会溢出 int32k1 k 2^31 - 1k 恒为正数取模运算语义确定解题思路前缀和 同余定理题目只要求判断是否存在不要求找出所有解因此无需枚举全部子数组。核心思路分三步前缀和表示子段和区间[i, j]内的元素和等于prefixSum[j] - prefixSum[i]其中prefixSum[i]表示前 i 个元素之和i取-1时前缀和为 0。只要两个前缀和之差是 k 的倍数对应的连续子数组就满足条件。同余定理转化prefixSum[j] - prefixSum[i]是 k 的倍数 ⟺prefixSum[j] % k prefixSum[i] % k。因此不需要保存完整的前缀和序列只需记录每个下标处前缀和除以 k 的余数即可。哈希表记录余数首次出现位置用 map 存储每个余数第一次出现的下标。当遍历到下标j时若当前余数已经在 map 中假设记录的下标为i则说明[i1, j]这一段的和是 k 的倍数再校验j - i 2是否满足长度至少为 2 的条件即可。之所以只保留余数首次出现的下标是因为子数组的长度要求是“至少为 2”保留最早的下标能让后续任意一个同余下标都获得最大的可用长度贪心成立且不遗漏解。Go 实现与源码解读仓库中的完整实现位于 523. Continuous Subarray Sum.gopackage leetcode func checkSubarraySum(nums []int, k int) bool { m : make(map[int]int) m[0] -1 sum : 0 for i, n : range nums { sum n if r, ok : m[sum%k]; ok { if i-2 r { return true } } else { m[sum%k] i } } return false }关键细节逐行剖析m[0] -1的作用这是整个实现最精妙的一行。前缀和数组在“第 -1 个元素”处视为 0余数为 0。它的作用是当某个前缀和本身就能被 k 整除时即余数为 0说明从数组开头到当前下标的整段就是 k 的倍数。此时用它减去的“第 -1 个位置的前缀和 0”恰好构成完整的合法子数组且长度判定可直接复用统一逻辑。例如nums [23, 2, 6, 4, 7], k 6遍历到下标 4 时sum 42sum % 6 0map 中余数 0 记录的下标为 -14 - 2 -1成立返回true对应示例 2 的整段。长度判定i-2 r同余的两个下标imap 中记录的较早下标与j当前下标对应的子数组是[i1, j]其长度为j - i。要求长度至少为 2即j - i 2代码中写成i - 2 rr 即记录的下标两者完全等价。注意这里不能直接返回true因为同余的较早下标可能紧邻当前下标长度为 1不满足“至少为 2”此时应继续向后遍历让同一余数遇到更远的同余下标。else分支保证“首次出现”只有当余数首次出现时才写入 map后续重复出现的同余下标一律忽略确保 map 中保存的始终是该余数最早的下标从而最大化后续长度判定的命中率。复杂度分析时间复杂度O(n)。数组只遍历一遍map 的读写均为常数时间其中 n 为nums.length。空间复杂度O(min(n, k))。map 中最多存储 k 个不同的余数实际不超过数组长度 n。测试用例验证仓库为本题配套了完整测试 523. Continuous Subarray Sum_test.go覆盖了 README 中的三个示例qs : []question523{ {para523{[]int{23, 2, 4, 6, 7}, 6}, ans523{true}}, // [2, 4] 和为 6 {para523{[]int{23, 2, 6, 4, 7}, 6}, ans523{true}}, // 整段和为 42 {para523{[]int{23, 2, 6, 4, 7}, 13}, ans523{false}}, }测试通过Test_Problem523遍历用例调用checkSubarraySum(p.nums, p.k)并与期望结果比对。可进入leetcode/0523.Continuous-Subarray-Sum目录后执行go test -v验证实现该包位于仓库的 leetcode 模块内运行go test ./leetcode/...亦可覆盖本题。边界情况与易错点长度为 1 的子数组不能算数例如nums [5, 0, 0], k 5中[5]本身是 5 的倍数但长度不足 2正确答案是true因为[0, 0]和为 0 是 5 的倍数且长度 2。i - 2 r正是为了排除这种单元素误判。0 永远是 k 的倍数当子段和为 0 时无论 k 取何值都满足条件示例中[0, 0]这类全零子数组要能被正确识别。余数可能为 0 但下标为 -1m[0] -1不是真实下标只是哨兵值长度判定公式天然兼容它。同类题目拓展与 560 的对照前缀和 哈希表是“连续子数组求和”系列题目的核心范式仓库中同类的典型题目是560. Subarray Sum Equals K题解文档、实现。两者对照可加深理解维度523本题560目标判断是否存在一个子数组和为 k 的倍数统计和为 k 的子数组个数判定条件prefixSum[j] % k prefixSum[i] % kprefixSum[j] - prefixSum[i] kmap 存储内容余数 → 首次出现下标前缀和 → 出现次数长度限制要求子数组长度至少为 2无长度限制数据特点nums[i] 0k 为正nums[i]可为负不能滑动窗口560 中由于nums[i]可能为负数无法使用滑动窗口同样退化为“前缀和 map 计数”的 O(n) 解法而 523 之所以同样用哈希表而非滑动窗口是因为“和的倍数”这一判定无法通过双指针单调收缩窗口来维护。小结LeetCode 523 的核心结论可以浓缩为一句话连续子数组的和是 k 的倍数 ⟺ 两端前缀和模 k 同余。基于此用 map 记录每个余数最早出现的下标一次线性扫描即可完成判定时间复杂度 O(n)、空间复杂度 O(min(n, k))。仓库中 完整实现 与 测试用例 可直接查阅、编译与运行该模式稍加变形即可迁移到 560、974和为 k 的倍数计数等系列题目。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 523：Continuous Subarray Sum —— Go 实现前缀和与同余定理判定 k 倍数子数组
LeetCode 523Continuous Subarray Sum —— Go 实现前缀和与同余定理判定 k 倍数子数组【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 leetcode/0523.Continuous-Subarray-Sum/README.md 的题解展开系统讲解LeetCode 523. Continuous Subarray Sum的完整解法如何用前缀和 同余定理 哈希表在 O(n) 时间内判断数组中是否存在长度至少为 2、且元素和为 k 的倍数的连续子数组。读完本文你将掌握该类「子数组和与 k 整除」问题的通用套路余数映射并能直接复用本仓库中可编译、可测试的 Go 实现。题目描述给定一个整数数组nums和一个整数k判断nums是否存在一个大小至少为 2的连续子数组其元素之和是k的倍数。若存在返回true否则返回false。关于倍数的定义整数x是k的倍数当且仅当存在整数n使得x n * k。特别地0永远是k的倍数——这一点在 k 恰好等于某个子段和时非常关键。示例示例 1输入: nums [23,2,4,6,7], k 6 输出: true 解释: [2, 4] 是一个长度为 2 的连续子数组其元素和为 6是 6 的倍数。示例 2输入: nums [23,2,6,4,7], k 6 输出: true 解释: [23, 2, 6, 4, 7] 是长度为 5 的连续子数组其元素和为 42 7 * 6是 6 的倍数。示例 3输入: nums [23,2,6,4,7], k 13 输出: false数据约束约束项取值范围对解法的影响nums.length1 nums.length 10^5需要 O(n) 或更优的算法O(n²) 会超时nums[i]0 nums[i] 10^9前缀和单调不减无负数干扰sum(nums[i])0 sum 2^31 - 1单次前缀和不会溢出 int32k1 k 2^31 - 1k 恒为正数取模运算语义确定解题思路前缀和 同余定理题目只要求判断是否存在不要求找出所有解因此无需枚举全部子数组。核心思路分三步前缀和表示子段和区间[i, j]内的元素和等于prefixSum[j] - prefixSum[i]其中prefixSum[i]表示前 i 个元素之和i取-1时前缀和为 0。只要两个前缀和之差是 k 的倍数对应的连续子数组就满足条件。同余定理转化prefixSum[j] - prefixSum[i]是 k 的倍数 ⟺prefixSum[j] % k prefixSum[i] % k。因此不需要保存完整的前缀和序列只需记录每个下标处前缀和除以 k 的余数即可。哈希表记录余数首次出现位置用 map 存储每个余数第一次出现的下标。当遍历到下标j时若当前余数已经在 map 中假设记录的下标为i则说明[i1, j]这一段的和是 k 的倍数再校验j - i 2是否满足长度至少为 2 的条件即可。之所以只保留余数首次出现的下标是因为子数组的长度要求是“至少为 2”保留最早的下标能让后续任意一个同余下标都获得最大的可用长度贪心成立且不遗漏解。Go 实现与源码解读仓库中的完整实现位于 523. Continuous Subarray Sum.gopackage leetcode func checkSubarraySum(nums []int, k int) bool { m : make(map[int]int) m[0] -1 sum : 0 for i, n : range nums { sum n if r, ok : m[sum%k]; ok { if i-2 r { return true } } else { m[sum%k] i } } return false }关键细节逐行剖析m[0] -1的作用这是整个实现最精妙的一行。前缀和数组在“第 -1 个元素”处视为 0余数为 0。它的作用是当某个前缀和本身就能被 k 整除时即余数为 0说明从数组开头到当前下标的整段就是 k 的倍数。此时用它减去的“第 -1 个位置的前缀和 0”恰好构成完整的合法子数组且长度判定可直接复用统一逻辑。例如nums [23, 2, 6, 4, 7], k 6遍历到下标 4 时sum 42sum % 6 0map 中余数 0 记录的下标为 -14 - 2 -1成立返回true对应示例 2 的整段。长度判定i-2 r同余的两个下标imap 中记录的较早下标与j当前下标对应的子数组是[i1, j]其长度为j - i。要求长度至少为 2即j - i 2代码中写成i - 2 rr 即记录的下标两者完全等价。注意这里不能直接返回true因为同余的较早下标可能紧邻当前下标长度为 1不满足“至少为 2”此时应继续向后遍历让同一余数遇到更远的同余下标。else分支保证“首次出现”只有当余数首次出现时才写入 map后续重复出现的同余下标一律忽略确保 map 中保存的始终是该余数最早的下标从而最大化后续长度判定的命中率。复杂度分析时间复杂度O(n)。数组只遍历一遍map 的读写均为常数时间其中 n 为nums.length。空间复杂度O(min(n, k))。map 中最多存储 k 个不同的余数实际不超过数组长度 n。测试用例验证仓库为本题配套了完整测试 523. Continuous Subarray Sum_test.go覆盖了 README 中的三个示例qs : []question523{ {para523{[]int{23, 2, 4, 6, 7}, 6}, ans523{true}}, // [2, 4] 和为 6 {para523{[]int{23, 2, 6, 4, 7}, 6}, ans523{true}}, // 整段和为 42 {para523{[]int{23, 2, 6, 4, 7}, 13}, ans523{false}}, }测试通过Test_Problem523遍历用例调用checkSubarraySum(p.nums, p.k)并与期望结果比对。可进入leetcode/0523.Continuous-Subarray-Sum目录后执行go test -v验证实现该包位于仓库的 leetcode 模块内运行go test ./leetcode/...亦可覆盖本题。边界情况与易错点长度为 1 的子数组不能算数例如nums [5, 0, 0], k 5中[5]本身是 5 的倍数但长度不足 2正确答案是true因为[0, 0]和为 0 是 5 的倍数且长度 2。i - 2 r正是为了排除这种单元素误判。0 永远是 k 的倍数当子段和为 0 时无论 k 取何值都满足条件示例中[0, 0]这类全零子数组要能被正确识别。余数可能为 0 但下标为 -1m[0] -1不是真实下标只是哨兵值长度判定公式天然兼容它。同类题目拓展与 560 的对照前缀和 哈希表是“连续子数组求和”系列题目的核心范式仓库中同类的典型题目是560. Subarray Sum Equals K题解文档、实现。两者对照可加深理解维度523本题560目标判断是否存在一个子数组和为 k 的倍数统计和为 k 的子数组个数判定条件prefixSum[j] % k prefixSum[i] % kprefixSum[j] - prefixSum[i] kmap 存储内容余数 → 首次出现下标前缀和 → 出现次数长度限制要求子数组长度至少为 2无长度限制数据特点nums[i] 0k 为正nums[i]可为负不能滑动窗口560 中由于nums[i]可能为负数无法使用滑动窗口同样退化为“前缀和 map 计数”的 O(n) 解法而 523 之所以同样用哈希表而非滑动窗口是因为“和的倍数”这一判定无法通过双指针单调收缩窗口来维护。小结LeetCode 523 的核心结论可以浓缩为一句话连续子数组的和是 k 的倍数 ⟺ 两端前缀和模 k 同余。基于此用 map 记录每个余数最早出现的下标一次线性扫描即可完成判定时间复杂度 O(n)、空间复杂度 O(min(n, k))。仓库中 完整实现 与 测试用例 可直接查阅、编译与运行该模式稍加变形即可迁移到 560、974和为 k 的倍数计数等系列题目。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考