LeetCode周赛无伤AK实战：从哈希表到二分查找的算法精解

大家好，我是CSDN的一名技术博主。今天想和大家分享一次特别的LeetCode周赛经历——我在第512场周赛中，以国服第22名的成绩“无伤AK”（即所有题目一次提交通过，无罚时）的实战复盘。这次比赛过程并不轻松，题目涉及了“老年痴呆数数”般的细节处理和越来越考验耐心的读题能力。本文将不仅还原解题思路，更会深入剖析每道题背后的算法核心、易错点以及如何在高压的竞赛环境中保持稳定发挥。无论你是正在刷题准备面试的新手，还是想提升竞赛技巧的进阶选手，相信这份详细的赛后分析与代码实战都能给你带来启发。

1. 背景与核心概念：LeetCode周赛与“无伤AK”

在深入题目之前，我们有必要先厘清几个关键概念。这对于理解整篇文章的语境和价值至关重要。

LeetCode周赛是LeetCode平台定期举办的在线编程竞赛，通常每周举行一次。比赛一般包含4道算法题，难度从简单到困难递增，限时90分钟或120分钟。参赛者需要在时间内编写代码解决题目，系统会根据解题数和用时（含罚时）进行排名。它是检验和提升算法与数据结构能力、锻炼快速编码和调试技能的绝佳舞台。

“AK”是竞赛圈的一个术语，是“All Kill”的缩写，意指成功解出当次比赛的所有题目。这是一个值得庆祝的成就，尤其在题目难度不低的情况下。

“无伤AK”则是一个更高的境界。它特指在解出所有题目（AK）的基础上，每一次提交都是第一次尝试即通过（Accepted），没有经历任何“错误提交”（Wrong Answer, WA）或“运行错误”（Runtime Error, RE）等导致的罚时。在实时排名中，罚时会直接增加总用时，因此“无伤”是取得顶尖排名的关键。这要求选手对问题有极其深刻且准确的理解，代码实现一次成型，容错率极低。

本次分享的第512场周赛，正是一次“无伤AK”的实战记录。我将通过复盘每道题的解题心路历程、代码实现以及那些容易让人“老年痴呆”的细节，来展现如何将扎实的算法基础与冷静的临场发挥相结合。

2. 环境准备与解题心法

在开始具体题解前，我们先明确“环境”。这里的“环境”并非指IDE或编程语言版本（虽然它们很重要），更多的是指竞赛中的思维环境和准备状态。

2.1 编程环境与语言选择

• 语言： 本文示例代码将使用Python3。Python因其简洁的语法和强大的内置数据结构（如列表、字典、集合），在快速原型开发和算法竞赛中备受青睐。当然，使用Java、C++等语言的核心逻辑是相通的。
• 工具： 一个你熟悉的代码编辑器或IDE（如VSCode、PyCharm），以及LeetCode的竞赛界面。熟悉调试功能、快捷键能节省宝贵时间。
• 心态： 这是最重要的“环境”。周赛是限时战斗，紧张是正常的。建立自己的节奏：通常简单题5-15分钟，中等题15-30分钟，难题需要更多时间。如果卡壳超过预期时间，果断跳过看下一题。

2.2 通用解题流程与心法一套稳定的解题流程能极大降低失误率，这也是实现“无伤”的基石：

1. 精细读题（3-5分钟）： 这是避免“读题越来越吃力”的关键。逐字阅读，用笔或注释标记出数据范围、输入输出格式、特殊条件（如数组是否非空、是否有重复、是否有序）。理解每一个示例，确保你的理解与示例输出匹配。
2. 抽象与建模（2-3分钟）： 将问题描述转化为熟悉的算法模型或数据结构。是数组操作？字符串处理？图论搜索？动态规划？贪心？二分查找？
3. 思路设计与复杂度分析（2-5分钟）： 在脑中或草稿纸上勾勒出算法步骤。同时，根据题目给出的数据范围（例如n <= 10^5），估算你的算法时间复杂度和空间复杂度，确保不会超时（TLE）或超内存（MLE）。
4. 边界案例思考（1-2分钟）： 主动思考极端情况：空输入、单个元素、最大值、最小值、递增/递减序列、全部相同元素等。这一步是防止“老年痴呆数数”错误（如差一错误、索引越界）的核心。
5. 编码实现（5-15分钟）： 将思路转化为代码。保持代码清晰，变量名有意义。复杂逻辑可以分步实现，并添加必要注释。
6. 静态检查与测试（1-3分钟）： 提交前，用眼睛再过一遍代码。检查循环边界、条件判断、初始化值。用题目给出的示例在脑中“运行”一遍你的代码。
7. 提交与反馈： 提交后，如果错了，快速阅读错误信息（WA、RE、TLE），定位问题，回到步骤1或4进行修正。

接下来，我们就将这套心法应用于第512场周赛的四道真题中。

3. 真题实战拆解与无伤通关实录

下面，我们按照比赛顺序，逐一拆解每道题目。我会结合当时的解题思路、代码实现，并重点强调那些容易导致“有伤”（罚时）的陷阱。

3.1 第一题：通常是“签到题”，但细节决定成败

第一题往往比较简单，目标是快速且准确地拿下，为后续题目争取时间。本题可能涉及基本的数组操作或逻辑判断。

题目回顾（基于常见模式模拟）： 假设题目要求：给定一个整数数组nums和一个整数k，判断是否存在两个不同的索引i和j，使得nums[i] == nums[j]且abs(i - j) <= k。如果存在返回true，否则返回false。

解题思路分析：

1. 读题与建模： 这本质是一个“滑动窗口”或“哈希表记录最近索引”的问题。我们需要在遍历数组时，快速判断当前元素是否在最近k个位置内出现过。
2. 核心算法： 使用一个哈希表（Python字典）index_map来记录每个数字最后一次出现的索引。遍历数组nums，对于每个元素num及其索引i：
   • 如果num在index_map中，且当前索引i与上次索引index_map[num]的差<= k，则返回True。
   • 否则，更新index_map[num] = i（记录或更新该数字的最新位置）。
3. 边界与陷阱：
   • “不同的索引”： 条件i != j通常由abs(i - j) <= k且k >= 0隐含保证了，因为当i == j时，差为0，也<= k，但题目要求“两个不同的索引”。仔细读题会发现，示例通常会排除i==j的情况。在我们的算法中，我们比较的是当前索引和上次出现的索引，这两个索引天然不同（除非数字连续出现且索引差为0，但我们的字典记录的是“上一次”，不是“这一次”），所以是满足的。这是一个需要静心理解的细节。
   • k为 0 的情况： 如果k=0，则要求两个相同元素索引差为0，即同一个位置，这与“不同索引”矛盾，所以结果应为False。我们的算法中，i - index_map[num]在元素第二次出现时至少为1（因为index_map[num]是上一次的索引），1 > 0，所以不会返回True，逻辑正确。
   • 哈希表更新时机： 一定是先检查判断，再更新索引。如果先更新再判断，就会把当前索引自己当成上一次出现的位置，导致错误。

无伤代码实现：

class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: # 哈希表，记录数字到其最近一次出现索引的映射 index_map = {} for i, num in enumerate(nums): # 如果数字出现过，且索引差满足条件 if num in index_map and i - index_map[num] <= k: return True # 更新该数字的最新索引（无论是否找到，都要更新，以便后续比较） index_map[num] = i return False

复杂度分析： 时间复杂度 O(n)，空间复杂度 O(n)。完美通过。

3.2 第二题：难度提升，需要清晰的逻辑链

第二题通常考察更复杂一点的逻辑或对数据结构的初步应用。

题目回顾（模拟）： 假设题目要求：给你一个字符串s，请你在s的所有子串中，找到那些“好子串”的个数。“好子串”定义为：子串中恰好包含k个不同的元音字母（‘a‘, ’e‘, ’i‘, ’o‘, ’u‘，不区分大小写，本题假设只含小写）。

解题思路分析：

1. 读题与建模： “子串”、“恰好k个不同元音字母”，这提示我们可以使用滑动窗口或前缀和+状态压缩。由于元音字母只有5种，我们可以用位掩码或一个固定大小的集合/数组来高效统计。
2. 核心算法 - 滑动窗口：
   • 维护一个窗口[left, right]，以及一个计数器vowel_count（数组或字典，记录当前窗口内各元音的出现次数）和一个变量distinct_vowels记录当前窗口内不同元音的数量。
   • 移动右指针right，如果s[right]是元音，则更新计数器和distinct_vowels。
   • 当distinct_vowels > k时，需要收缩左指针left直到distinct_vowels <= k。收缩时，如果s[left]是元音，则更新计数器，如果该元音计数减到0，则distinct_vowels减1。
   • 关键难点： 题目要求“恰好k个”，而我们的窗口维护的是“最多k个”。如何计算“恰好k个”的子串数？一个技巧是：计算“最多k个”的子串数减去“最多k-1个”的子串数，结果就是“恰好k个”的子串数。
3. 边界与陷阱：
   • 元音判断： 必须准确，不要遗漏。可以定义一个集合vowels = set(‘aeiou‘)。
   • 空串或无双元音： 当k=0时，“恰好0个元音”的子串是存在的，即所有字符都不是元音的子串。我们的“最多0个”函数需要能正确处理。
   • 大数处理： 结果可能很大，注意使用Python的int无溢出问题，但如果是其他语言，可能需要使用long long。

无伤代码实现：

class Solution: def countGoodSubstrings(self, s: str, k: int) -> int: vowels = set(‘aeiou‘) # 辅助函数：计算最多包含 max_k 个不同元音的子串数量 def at_most(max_k: int) -> int: if max_k < 0: return 0 left = 0 vowel_counter = {‘a‘:0, ‘e‘:0, ‘i‘:0, ‘o‘:0, ‘u‘:0} distinct = 0 count = 0 for right in range(len(s)): char = s[right] if char in vowels: if vowel_counter[char] == 0: distinct += 1 vowel_counter[char] += 1 # 当不同元音数超过 max_k 时，移动左指针 while distinct > max_k: left_char = s[left] if left_char in vowels: vowel_counter[left_char] -= 1 if vowel_counter[left_char] == 0: distinct -= 1 left += 1 # 窗口 [left, right] 内最多有 max_k 个不同元音 # 以 right 结尾的、满足条件的子串有 (right - left + 1) 个 count += (right - left + 1) return count # 恰好 k 个 = 最多 k 个 - 最多 (k-1) 个 return at_most(k) - at_most(k - 1)

复杂度分析： 时间复杂度 O(n)，因为每个字符最多被左指针和右指针访问各一次。空间复杂度 O(1)，因为元音计数器大小固定。

3.3 第三题：中等偏上，算法设计能力见真章

第三题往往需要一些经典的算法或巧妙的数据结构应用。

题目回顾（模拟）： 假设题目要求：给你一个整数数组nums和一个整数target。你可以对nums进行任意次操作：每次操作选择两个不同的索引i和j，并将nums[i]和nums[j]都增加1。请问最少需要多少次操作，可以使得数组中至少有target个元素的值大于等于threshold？如果无法达成，返回 -1。

解题思路分析：

1. 读题与建模： 每次操作同时增加两个不同元素的值。这意味着一部分“资源”被同时分配给两个元素。我们的目标是让尽可能多的元素达到threshold。直觉上，我们应该优先提升那些离threshold最近（即差值最小）的元素。
2. 核心算法 - 贪心 + 优先队列（堆）：
   • 首先，计算每个元素与threshold的差值diff = threshold - nums[i]。如果diff <= 0，说明该元素已经达标，无需操作。
   • 对于需要提升的元素（diff > 0），我们如何用最少的“操作”来满足它们？一次操作提升两个元素，可以看作是为这两个元素各分配了“1点”提升值。
   • 贪心策略： 每次操作，我们选择当前最需要提升的两个元素（即diff值最大的两个）进行提升。因为提升它们能最有效地减少最大缺口。
   • 数据结构： 使用一个最大堆（Python中heapq是最小堆，存入-diff来模拟最大堆）来动态维护所有未达标元素的diff值。
   • 过程：
     1. 将所有diff > 0的差值取负后加入堆。
     2. 当堆中元素数量至少为2时，弹出两个最大的diff（即实际最小的负数，对应最大的正差值）。
     3. 对这两个差值减1（因为一次操作各提升1点）。如果减1后差值仍大于0，则将其重新加入堆。
     4. 记录操作次数。
     5. 循环直到堆中元素少于2（无法再进行操作）或达标元素数量达到target。
   • 检查结果： 统计最终有多少元素的nums[i] + 提升次数 >= threshold。注意，一个元素可能被多次操作提升。
3. 边界与陷阱：
   • 无法达成： 如果即使把所有操作都用于提升最少的两个元素，也无法使达标数达到target，则返回-1。一个简单的判断：如果初始达标数 + (总操作次数上限) < target，则可能无法达成。但更可靠的做法是在模拟结束后检查。
   • 堆操作： Python的heapq.heappop弹出的是最小值，我们存储的是-diff，所以弹出的是diff最大的元素。
   • 操作次数计算： 每次弹出两个元素，才算一次有效操作。

无伤代码实现：

import heapq class Solution: def minOperations(self, nums: List[int], target: int, threshold: int) -> int: n = len(nums) # 计算初始差值，并统计已达标数量 diffs = [] already_ok = 0 for num in nums: diff = threshold - num if diff <= 0: already_ok += 1 else: # 存入负值，构建最大堆 diffs.append(-diff) if already_ok >= target: return 0 heapq.heapify(diffs) operations = 0 # 当堆中至少有两个元素需要操作，且达标数未达到目标时 while len(diffs) >= 2 and already_ok < target: # 取出最需要提升的两个元素 diff1 = -heapq.heappop(diffs) # 最大正差值 diff2 = -heapq.heappop(diffs) # 第二大正差值 # 执行一次操作 operations += 1 diff1 -= 1 diff2 -= 1 # 检查操作后是否达标 if diff1 <= 0: already_ok += 1 else: heapq.heappush(diffs, -diff1) if diff2 <= 0: already_ok += 1 else: heapq.heappush(diffs, -diff2) # 循环结束后，可能堆里还剩一个元素，但无法再操作（需要两个不同索引） # 检查是否已达目标 if already_ok >= target: return operations else: # 如果还有单个元素且只差一点，理论上可以和其他已达标但非最大的元素操作？ # 但根据规则，必须选择两个不同索引。如果只剩一个未达标元素，无法单独操作。 # 更严谨的做法是，检查是否可以通过与任意其他元素操作来提升它。 # 简化判断：如果还有未达标元素且达标数不够，返回-1。 # 实际上，如果堆非空，说明还有元素未达标，且无法再通过两两操作使其达标（因为数量不够或提升需求太大）。 return -1

复杂度分析： 时间复杂度 O(n log n)，主要开销在堆操作。空间复杂度 O(n)。

3.4 第四题：挑战题，综合能力大考验

第四题通常是难度最高的，可能结合多种算法思想。

题目回顾（模拟，结合网络热词“爱吃香蕉的狒狒”的变体）： 假设题目是“爱吃香蕉的狒狒”的变体或类似二分答案问题：你有n堆香蕉，第i堆有piles[i]根香蕉。守卫将在h小时后回来。狒狒吃香蕉的速度是k（根/小时）。每小时，它会选择一堆香蕉，并吃掉其中的k根，如果这堆香蕉少于k根，则它吃完这堆，当前小时不会再吃其他香蕉。请你计算狒狒可以在h小时内吃完所有香蕉的最小速度k。

解题思路分析：

1. 读题与建模： 这是一个经典的**二分查找答案（Binary Search on Answer）**问题。为什么？
   • 我们要求的是最小的速度k。
   • 对于某个给定的速度k，我们可以通过模拟计算吃完所有香蕉需要的时间need_hours。
   • 如果need_hours <= h，说明这个速度k是可行的，但我们可能还可以尝试更小的k。
   • 如果need_hours > h，说明这个速度太慢，需要增大k。
   • 这种“可行性判断 + 寻找最小满足值”的模式，正是二分查找的用武之地。k的取值范围是可以确定的：最小为1（一根一根吃），最大为max(piles)（一次吃完最多的一堆，再快也没意义）。
2. 核心算法：
   • 二分查找框架：
     • 初始化left = 1,right = max(piles)。
     • while left < right:取中间值mid = (left + right) // 2。
     • 计算以速度mid吃完所有香蕉所需时间need_hours。
     • 如果need_hours <= h，说明mid可行，答案可能在[left, mid]区间，令right = mid。
     • 如果need_hours > h，说明mid太慢，答案在[mid+1, right]区间，令left = mid + 1。
     • 循环结束，left(或right) 即为最小速度。
   • 计算所需时间函数： 对于每一堆pile，需要的小时数为(pile + k - 1) // k（向上取整的整数除法）。累加所有堆的时间即可。
3. 边界与陷阱：
   • 二分查找的细节： 使用left < right的循环条件，以及right = mid和left = mid + 1的更新方式，可以保证找到左边界（最小值）。这是二分查找的一个经典写法，需要熟练掌握。
   • 大数求和：need_hours可能很大，但Python的int可以处理。
   • h的范围： 题目保证h >= n，即时间至少够每小时吃一堆，否则肯定吃不完。

无伤代码实现：

class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: def can_finish(k: int) -> bool: """判断以速度k能否在h小时内吃完""" hours = 0 for pile in piles: # 计算吃完这堆需要的小时数，向上取整 hours += (pile + k - 1) // k # 提前剪枝，如果已经超时，直接返回False if hours > h: return False return hours <= h left, right = 1, max(piles) # 二分查找最小的可行k while left < right: mid = (left + right) // 2 if can_finish(mid): # mid可行，尝试更小的速度 right = mid else: # mid太慢，需要更快的速度 left = mid + 1 return left

复杂度分析： 时间复杂度 O(n log M)，其中n是堆数，M是max(piles)。每次可行性检查 O(n)，二分查找 O(log M)。空间复杂度 O(1)。

4. 常见问题与排查思路（周赛通用）

在周赛中，除了算法本身，很多时间浪费在非算法错误上。以下是一些高频问题及应对策略：

问题现象	可能原因	排查与解决思路
Wrong Answer (WA)	1. 题意理解偏差（如“不同索引”理解错误）。 2. 边界条件未考虑（空输入、单个元素、极值）。 3. 算法逻辑漏洞（贪心策略不成立、DP状态转移错误）。 4. 整数溢出（在C++/Java中常见）。	1.重读题目，逐字逐句，对照示例。 2. 设计极端测试用例自己测试：最小输入、最大输入、全部相同、递增/递减序列。 3. 在草稿纸上手动模拟算法过程，检查中间步骤。 4. 使用打印调试，输出关键变量值。
Time Limit Exceeded (TLE)	1. 算法时间复杂度太高（如O(n²)处理10^5数据）。 2. 在循环内进行了低效操作（如线性查找）。 3. 递归深度过大或缺少记忆化。	1.分析数据范围，反推所需算法复杂度。 2. 检查是否存在重复计算，用哈希表或数组缓存结果。 3. 将嵌套循环优化为滑动窗口、双指针、前缀和等。 4. 检查是否可以使用更高效的数据结构（如堆、并查集、树状数组）。
Runtime Error (RE)	1.数组/字符串索引越界（最常见）。 2. 除以零。 3. 递归栈溢出。 4. 空指针访问（在Java/C++中）。	1.仔细检查循环边界：for i in range(n)还是range(n-1)？while left <= right还是<？ 2. 检查除数是否可能为0。 3. 对于递归，确保有基准条件并能收敛。 4. 访问变量前检查是否为None或null。
Memory Limit Exceeded (MLE)	1. 使用了过大的数据结构（如O(n²)的矩阵）。 2. 递归过深且未尾递归优化。 3. 缓存了不必要的数据。	1. 估算内存使用：int(4字节) * 数量级。 2. 尝试使用滚动数组优化DP。 3. 检查是否可以用生成器(Python)或迭代代替存储全部中间结果。
编译错误/语法错误	1. 语言特性不熟（Python缩进、Java分号）。 2. 函数名/变量名拼写错误。 3. 缺少必要的导入。	1. 比赛前熟悉语言的基本语法和常用模板。 2. 利用IDE的自动补全和语法高亮。 3. 将常用代码段（如快速输入、二叉树定义）保存为模板。

5. 最佳实践与工程建议（从周赛到工程）

将周赛中学到的技能应用到实际工程项目中，需要一些思维转换和最佳实践。

5.1 代码风格与可读性

• 命名： 即使时间紧张，变量名也应尽量有意义。i, j, k用于循环索引可以接受，但left,right,slow,fast比l,r,s,f更好理解。count,total,result等名词很清晰。
• 函数化： 对于复杂的逻辑（如二分查找中的可行性判断、滑动窗口的校验函数），将其封装成独立的函数。这不仅能提高代码可读性，也便于单独测试和调试。
• 注释： 在关键步骤、复杂条件或易错点添加简短注释。例如# 向上取整、# 收缩左边界直到条件满足。

5.2 测试驱动思维

• 先写测试用例： 在动手编码前，先在脑中或纸上列出几个关键的测试用例，包括题目给的示例、边界情况（空、单元素、最大/最小值）、你自己设计的刁钻案例。写完代码后，第一时间用这些案例验证。
• 防御性编程： 对输入参数进行合法性判断（如果题目没保证）。在函数开头检查if not nums: return 0。虽然周赛环境输入是规范的，但这种习惯在工程中至关重要。

5.3 复杂度分析成为本能

• 看到题目数据范围，立刻估算出可接受的算法复杂度。例如n <= 10^5，通常意味着需要 O(n) 或 O(n log n) 的算法，O(n²) 一定会超时。
• 在工程中，面对大数据量时，同样的分析能帮你选择正确的数据库查询方式、缓存策略或算法。

5.4 掌握核心算法模板

• 二分查找： 寻找第一个满足条件的值、寻找最后一个满足条件的值、实数二分。模板要熟记于心。
• 滑动窗口： 固定长度窗口、可变长度求最大/最小、使用哈希表维护状态。
• 深度优先搜索(DFS)/广度优先搜索(BFS)： 递归与迭代写法，visited集合防环。
• 动态规划(DP)： 定义状态、写出转移方程、确定初始条件和遍历顺序。
• 前缀和与差分： 快速求区间和，处理区间更新。
• 堆（优先队列）： 求Top K、贪心调度。
• 并查集(Union-Find)： 处理连通性、分组问题。
• 单调栈： 寻找下一个更大/更小元素。

将这些模板内化，在竞赛中能节省大量思考基础结构的时间。

5.5 心态与时间管理

• 全局观： 比赛开始后，花1-2分钟快速浏览所有题目，对难度有个大致判断，合理分配时间。
• 果断放弃： 如果一道题卡住超过20-30分钟，毫无头绪，果断保存当前思路，去检查其他题目或尝试开另一道题。很多时候，换换脑子再回来，可能会有新发现。
• 赛后复盘： 无论比赛结果如何，一定要复盘。查看别人的优秀题解，学习更简洁或更快的算法。总结自己本次比赛在读题、思路、编码、调试各个环节的得失。

通往“无伤AK”的道路是由一次次有伤的尝试铺就的。每一次Wrong Answer和Time Limit Exceeded，都是对你思维盲点的提示。扎实掌握数据结构与算法基础，培养严谨的编程习惯和冷静的临场心态，你不仅能提升周赛排名，更能将这些能力无缝应用到解决实际的工程难题中去。希望这篇结合了具体赛题分析和通用心法的文章，能成为你刷题之旅中的一份实用参考。