企业官网建设流程全解析

• 科学计算

本篇文章以 力扣双周赛 192 C 题题解文档 为骨架，围绕「至多取反一个元素后，和能被 k 整除的最长子数组」这一经典前缀和 + 哈希表问题，完整还原思路、四种语言实现、复杂度分析与仓库内的自动化测试证据。读完本文，你将掌握「前缀和模 k 首次出现位置」这一可迁移的计数技巧，并理解如何用枚举取反元素的方式把单次判定扩展为全局最优，同时学会借助 codeforces-go 仓库的测试框架验证算法正确性。

题目背景：力扣双周赛 192 的 C 题

本题来自 2025 年力扣第 192 场双周赛，在 leetcode/biweekly/192/README.md 中，作者（灵茶山艾府）给出了 Q1～Q4 四题的完整题解导航，本题为 Q3。从 测试文件 顶部的注释可以确认题目全称为Longest Subarray Divisible by K With at Most One Negation I，对应仓库路径为leetcode/biweekly/192/c/，目录下包含四份文件：

题目大意（由题名与题解思路推断）：给定整数数组nums和整数k，允许至多将一个元素取反（x变为-x），求操作之后数组中「和能被k整除」的最长连续子数组长度。允许不取反任何元素。

核心思路：枚举取反元素 + 前缀和模 k

本题解法的骨架是经典题974. 和可被 K 整除的子数组，题解文档第一句便点明："枚举取反的元素是nums[i]，随后做法类似 974"。

原型：子数组和可被 k 整除 ⟺ 前缀和模 k 相等

设前缀和P[0] = 0，P[i] = nums[0] + ... + nums[i-1]。子数组[l, r)的和为P[r] - P[l]，它可被k整除，当且仅当：

(P[r] - P[l]) % k == 0 ⟺ P[r] % k == P[l] % k

因此，只要两个前缀和模k的值相同，它们夹出的子数组和就必然能被k整除。用一个哈希表firstPos记录每个模值首次出现的下标，扫描过程中一旦再次遇到相同模值，就用当前位置减首次出现下标得到一段候选子数组，取最大值即为答案。这也是为什么代码中反复出现"前缀和 % k 首次出现的下标"这一注释。

本题扩展：枚举哪个元素被取反

单次扫描只能解决"不取反"的情况。取反nums[i]后，整个数组的元素序列发生了变化，无法直接用原前缀和。最朴素而正确的做法是：

1. 先在不取反的情况下求一遍最长可整除子数组；
2. 枚举i ∈ [0, n)，把nums[i]取反，重新求一遍最长可整除子数组，取所有结果的最大值；
3. 每次取反后立即复原，保证枚举互不影响。

这样把「全局最优」转化为「n + 1 次单点判定」，每次判定仍用前缀和 + 哈希表完成，逻辑清晰、正确性直观。

多语言实现

题解文档给出了 Python、Java、C++、Go 四种实现，这里完整继承并补充关键细节。

Python

class Solution: # 做法类似 974. 和可被 K 整除的子数组 def longestSubarrayDivByK(self, nums: list[int], k: int) -> int: first_pos = {0: -1} # 前缀和 % k 首次出现的下标 s = 0 # 前缀和 res = 0 for r, x in enumerate(nums): s = (s + x) % k if s in first_pos: res = max(res, r - first_pos[s]) else: first_pos[s] = r return res def longestSubarray(self, nums: list[int], k: int) -> int: # 不取反 ans = self.longestSubarrayDivByK(nums, k) # 枚举取反元素 for i in range(len(nums)): nums[i] *= -1 # 取反 ans = max(ans, self.longestSubarrayDivByK(nums, k)) nums[i] *= -1 # 复原 return ans

Python 的%运算符结果恒为非负，因此s = (s + x) % k无需额外的非负化处理。

Java

class Solution { public int longestSubarrayDivByK(int[] nums, int k) { Map<Integer, Integer> firstPos = new HashMap<>(); firstPos.put(0, -1); // 前缀和 % k 首次出现的下标 int sum = 0; // 前缀和 int res = 0; for (int r = 0; r < nums.length; r++) { sum = (sum + nums[r] % k + k) % k; // 保证 sum 非负 Integer l = firstPos.get(sum); if (l != null) { res = Math.max(res, r - l); } else { firstPos.put(sum, r); } } return res; } public int longestSubarray(int[] nums, int k) { // 不取反 int ans = longestSubarrayDivByK(nums, k); // 枚举取反元素 for (int i = 0; i < nums.length; i++) { nums[i] *= -1; // 取反 ans = Math.max(ans, longestSubarrayDivByK(nums, k)); nums[i] *= -1; // 复原 } return ans; } }

Java 的%对负数结果仍可能为负（如-1 % 3 == -1），因此用(sum + nums[r] % k + k) % k把前缀和模值拉回[0, k)。firstPos.put(0, -1)用虚拟哨兵表示"空前缀"，使从 0 开始的合法子数组也能被正确计算。

C++

class Solution { vector<int> first_pos; // 哈希表超时了，改用 vector // 类似 974. 和可被 K 整除的子数组 int longestSubarrayDivByK(vector<int>& nums, int k) { ranges::fill(first_pos, -2); first_pos[0] = -1; int s = 0; // 前缀和 int res = 0; for (int r = 0; r < nums.size(); r++) { s = (s + nums[r] % k + k) % k; // 保证 s 非负 int l = first_pos[s]; if (l != -2) { res = max(res, r - l); } else { first_pos[s] = r; } } return res; } public: int longestSubarray(vector<int>& nums, int k) { // 不取反 first_pos.resize(k); int ans = longestSubarrayDivByK(nums, k); // 枚举取反元素 for (int i = 0; i < nums.size(); i++) { nums[i] *= -1; // 取反 ans = max(ans, longestSubarrayDivByK(nums, k)); nums[i] *= -1; // 复原 } return ans; } };

C++ 版本有一个值得注意的实战细节：模值范围只有k种，作者在注释中说明"哈希表超时了，改用 vector"，即用定长数组first_pos（长度k）取代哈希表，配合ranges::fill(first_pos, -2)将"未出现"标记为-2，O(k)的复位成本远低于哈希表在极端数据下的开销，这也是竞赛代码的常见取舍。

Go

// 做法类似 974. 和可被 K 整除的子数组 func longestSubarrayDivByK(nums []int, k int) (res int) { firstPos := map[int]int{0: -1} // 前缀和 % k 首次出现的下标 sum := 0 // 前缀和 for r, x := range nums { sum = (sum + x%k + k) % k // 保证 sum 非负 l, ok := firstPos[sum] if ok { res = max(res, r-l) } else { firstPos[sum] = r } } return } func longestSubarray(nums []int, k int) int { // 不取反 ans := longestSubarrayDivByK(nums, k) // 枚举取反元素 for i := range nums { nums[i] *= -1 // 取反 ans = max(ans, longestSubarrayDivByK(nums, k)) nums[i] *= -1 // 复原 } return ans }

Go 中%对负数的结果同样可负，因此与 Java 一致采用(sum + x%k + k) % k的非负化写法。代码使用了内置泛型函数max（Go 1.21+ 才提供），运行本仓库代码时需注意 Go 版本要求。

复杂度分析

题解文档给出明确结论：

• 时间复杂度：O(n²)，其中n是nums的长度——外层枚举n个取反位置，每次内层做一次O(n)的前缀和扫描；
• 空间复杂度：O(n)，用于存储哈希表（实际模值种数不超过min(n, k)）。

在n较大时该做法仍显昂贵，题解文档因此在「附」一节给出了更优的枚举前缀和方案（见下文）。

仓库源码与自动化测试验证

题解并非纸上谈兵，仓库为其配齐了实现、数据与测试框架，可直接验证正确性。

源码与文档一致

Go 实现源码 与文档中的 Go 代码完全一致：longestSubarrayDivByK（c.go）实现单次前缀和 + 哈希表扫描，longestSubarray（c.go）负责枚举取反。可以说文档即源码、源码即文档。

测试数据与手算核对

测试数据文件 包含 3 组用例，格式为「nums/k/ 期望答案」：

以第一组为例手算核对：不取反时前缀和模 3 序列为1, 2, 1，最长相同模值间距为 2；枚举取反nums[2]后数组变为[4,1,-2]，前缀和模 3 序列为1, 2, 0，0首次出现在哨兵下标-1、当前位置下标2，长度2 - (-1) = 3，符合期望。

测试框架

测试入口 由copypasta/template/leetcode/generator_test.go生成，调用 testutil.RunLeetCodeFuncWithFile：该函数读取c.txt，按「参数行数 + 结果行数」为一组切分用例（见 leetcode.go 的分组逻辑），再用反射把每行解析为函数参数并断言输出。仓库内运行验证命令：

go test ./leetcode/biweekly/192/c/

进阶优化：O(n + min(n,k)²) 枚举前缀和

题解文档「附」一节指出：还可以枚举取反的元素，做到O(n + min(n,k)²)的时间复杂度，并且"可以通过本题和下一题"（即双周赛 192 的 Q4，仓库中对应 leetcode/biweekly/192/d 目录）。文档标注"思路及多语言代码稍后补充"，仅给出 Go 实现，这里完整继承并依据代码结构补充解读：

func longestSubarray(nums []int, k int) (ans int) { // 记录前缀和 % k 最后一次出现的下标 lastPos := make([]int, k) for i := range lastPos { lastPos[i] = -1 } lastPos[0] = 0 sum := 0 for i, x := range nums { x = x%k + k nums[i] = x // 保证 nums[i] 非负 sum = (sum + x) % k lastPos[sum] = i + 1 } // 记录前缀和 % k 首次出现的下标 firstPos := make([]int, k) for i := range firstPos { firstPos[i] = -1 } type pair struct{ sum, l int } first := []pair{{}} visTime := make([]int, k) t := 0 sum = 0 for i, x := range nums { // 发现新的前缀和 % k if firstPos[sum] < 0 { firstPos[sum] = i first = append(first, pair{sum, i}) t++ } sum = (sum + x) % k if l := firstPos[sum]; l >= 0 { ans = max(ans, i+1-l) // 不取反的情况 } y := x * 2 % k if visTime[y] == t { // 没有发现新的前缀和 % k，不考虑重复的 2x % k continue } visTime[y] = t for _, p := range first { r := lastPos[(p.sum+y)%k] if r > i { ans = max(ans, r-p.l) } } } return }

从代码结构可以读出该优化的三个关键设计：

1. 取反转化为模k上的位移：取反元素x等价于在该元素的区间和上减去2x。把x非负化为x%k + k后，区间和模k可被整除的条件就转化为「右端点前缀和模值 ≡ 左端点前缀和模值 +2x(mod k)」。代码中y := x * 2 % k正是这个位移量。
2. 两张定长表配合查询：firstPos记录每个模值首次出现的下标（左端点候选），lastPos记录每个模值最后一次出现的下标（右端点候选）；对每个枚举位置i，遍历已发现的所有"首次出现"模值p.sum，用lastPos[(p.sum+y)%k]直接查出最长右端点，避免全量扫描。
3. visTime按轮去重：以t（已发现新前缀和模值的轮次计数）为时间戳，保证在同一轮发现区间内每个y只处理一次，剔除重复计算，从而把内层开销控制在与"不同模值种数"相关，而不是与数组长度相关。

注意该优化后的代码刻意把nums[i]改写为非负模值，破坏了原数组，因此它更适合作为赛内提交解法而非需要保留原值的场景。

专题训练：前缀和与哈希表刷题路线

题解文档的「专题训练」一节将该题归入灵茶山艾府数据结构题单的「§1.2 前缀和与哈希表」，建议把这类题目放在一起系统性练习，巩固以下可迁移能力：

• 子数组和可整除 ⟺ 前缀和模值相等（如 974）；
• 子数组和为定值 ⟺ 前缀和差值（哈希表计数/首末次出现位置）；
• 负数取模的非负化处理（(x % k + k) % k）；
• 枚举一个"修改点"时，如何复用前缀和信息而非每次全量重扫。

文档「分类题单」还给出了覆盖各知识点的 12 个刷题专题（原文为链接形式，此处转述）：滑动窗口与双指针、二分算法、单调栈、网格图（DFS/BFS）、位运算、图论算法、动态规划、常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）、数学算法、贪心与思维、链表树与回溯、字符串（KMP/Z 函数/Manacher/字符串哈希/AC 自动机等）。

在 codeforces-go 仓库中，copypasta/目录沉淀了大量可直接复用的对应实现，例如 前缀和相关的 treap 数据结构、树状数组、线段树 等；而leetcode/weekly/与leetcode/biweekly/下按场次组织的题解 + 测试文件结构，正是刷题时"写一遍、测一遍、沉淀一份"的最佳实践范本。读者可沿着这条路线，把本篇文章的前缀和 + 哈希表套路应用到更多子数组计数与最值问题中。

• 科学计算