LeetCode 457 环形数组是否存在循环图论建模、暴力搜索与原地标记三种解法的完整剖析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南围绕 LeetCode 457「环形数组是否存在循环」Circular Array Loop展开结合 leetcode 仓库中收录的题解文档 problems/457.circular-array-loop.md从题目建模、暴力解法、空间优化到原地标记算法逐层深入。读完本文你将掌握把数组下标跳跃问题抽象为有向图找环的通用思路、Python 实现中异或判号与统一取模的技巧以及如何用原地标记把时间与额外空间同时优化到 O(n) 与 O(1)。题目解读三步移动规则与循环的三个硬性条件题目给出一个不含 0 的环形数组nums每个nums[i]表示位于下标 i 的角色应移动的步数nums[i]为正数时向前下标递增方向移动|nums[i]|步nums[i]为负数时向后下标递减方向移动|nums[i]|步数组是环形的从最后一个元素向前移动一步会到达第一个元素从第一个元素向后移动一步会到达最后一个元素。数组中存在循环需要同时满足三个条件存在长度为 k 的下标序列seq[0] - seq[1] - ... - seq[k-1] - seq[0] - ...即移动规则会诱导出一组重复下标序列序列中所有nums[seq[j]]要么全正、要么全负方向一致循环长度k 1单个下标原地踏步i - i不构成循环。对照三个示例可以直观理解判定逻辑输入nums [2,-1,1,2,2]输出true存在循环0 - 2 - 3 - 0长度为 3输入nums [-1,2]输出false下标 1 上1 - 1是长度为 1 的自环违反k 1输入nums [-2,1,-1,-2,-2]输出false1 - 2 - 1虽然成环但nums[1]为正而nums[2]为负违反全正或全负。数据范围约束为1 nums.length 5000、-1000 nums[i] 1000且nums[i] ! 0。题目进阶要求设计时间复杂度 O(n)、额外空间复杂度 O(1) 的算法这正是解法三的目标。图论建模把下标跳跃转化为有向图找环前置知识只有一条图。本题的关键洞察在于nums数组天然定义了一个有向图每个下标i是一个顶点从顶点i出发有一条有向边指向下一跳下标next(i) ((i nums[i]) % n n) % n每个顶点出度恰好为 1因为nums[i] ! 0下一跳必然存在且不是自身之外的非法位置。于是数组中是否存在循环等价于这个有向图中是否存在长度大于 1 的环且环上所有边的方向一致全正或全负。每个顶点出度为 1 的性质保证了从任意起点出发沿着边游走必然要么进入一个环要么走入此前访问过的节点——这正是各类检测算法可行性的根基。求下一跳下标时原题解采用统一写法((cur nums[cur]) % n n) % n用两次取模把向前越界和向后越界合并处理避免为两种越界分别写分支这是值得复用的编码技巧。解法一暴力搜索从每个起点出发探测环思路最朴素的做法是逐一检查从索引0, 1, ..., n-1出发的情况判断其能否构成长度至少为 2 的环整体框架只有四行for i in range(n): if can(i): return True return Falsecan(i)的功能是检查从 i 开始是否存在一条长度至少为 2 的循环。检查是否有环本质上是标准的图搜索问题直接套用 DFS 模板即可。实现时有三个容易踩的坑方向一致性由于环内元素必须同正同负可以记录起点的正负号如果遍历过程中遇到符号相反的nums值则提前退出环长约束环大小小于 2 时必须返回 False因此要记录走过的步数代码中的steps就是环的大小环形越界数组是环形的向前、向后两种越界需要分别处理为统一代码使用((cur nums[cur]) % n n) % n计算下一跳。代码Python3class Solution: def circularArrayLoop(self, nums: List[int]) - bool: def can(cur, start, steps): if nums[cur] ^ nums[start] 0: return False if cur start and steps ! 0: return steps 1 if cur in visited: return False visited.add(cur) return can(((cur nums[cur]) % n n ) % n, start, steps 1) n len(nums) visited None for i in range(n): visited set() if can(i, i, 0): return True return False代码中的关键细节值得展开nums[cur] ^ nums[start] 0判断同号Python 整数采用补码表示异或结果的最高位符号位为 1 说明两数一正一负此时提前返回 False。这是一个比分别比较正负更紧凑的位运算写法cur start and steps ! 0判断回到起点steps 0表示尚未出发此时不算成环只有走回起点且steps 1才算找到合法循环visited集合防死循环每个起点开启一轮新的visited一旦走入已访问节点且不是起点说明该路径不可能再形成新的环直接剪枝。复杂度分析令 n 为数组长度时间复杂度$O(n^2)$。每个起点最多探测 O(n) 个节点共 n 个起点空间复杂度$O(n)$。每轮 DFS 需要 visited 集合递归调用栈最坏深度为 n。解法二空间优化——用步数上限替代 visited思路解法一的空间开销来自visited集合。原题解给出了一个巧妙的替代思路如果steps大于 n 则一定不存在解可直接返回 False。为什么成立每个节点出度为 1从起点出发游走如果走了超过 n 步仍未回到起点、也未遇到方向不一致的节点那么由抽屉原理必然已重复访问某个节点——而一旦重复访问又未回到起点后续只会在这个已探明的无环路径上打转不可能再产生新的环。因此用steps n判断无解可以省掉visited数组。代码Python3class Solution: def circularArrayLoop(self, nums: List[int]) - bool: def can(cur, start, steps): if nums[cur] ^ nums[start] 0: return False if cur start and steps ! 0: return steps 1 if steps n: return False return can(((cur nums[cur]) % n n ) % n, start, steps 1) n len(nums) for i in range(n): if can(i, i, 0): return True return False原题解特别说明这种写法减少了空间但时间复杂度常数项比解法一差因此不推荐作为首选仅作参考。复杂度分析令 n 为数组长度时间复杂度$O(n^2)$。每个起点最坏需要探测 n 1 步才触发steps n剪枝空间复杂度$O(1)$不考虑递归调用栈。相比解法一省去了 visited 集合。解法三原地标记——哈希表语义与值域映射思路解法一、二的时间瓶颈在于每个起点都可能重复遍历大量已被判定无环的节点。原题解提出用哈希表visited记录访问情况其中 key 为索引、value 为起始点 start从而把时间复杂度降到 O(n)若visited[cur] start为真说明 cur 是在当前轮被标记访问的路径回到了本轮起点直接返回 true若visited中已有 cur 但 value 不是 start说明 cur 是之前某轮标记的——之前轮已经检查过经过 cur 不存在环因此直接返回 false 即可。使用 visited 后每个点最多被处理一次整体时间复杂度降到 O(n)。进一步的优化是原地标记不额外开辟 visited而是把数组本身改造成标记位。实现方式是把数组值映射到题目值域之外的数——以本题为例nums[i]的范围是[-1000, 1000]加上 5000 后得到[4000, 6000]与原始值域完全不相交不会与真实数据混淆。标记时写入nums[cur] start 5000用当前轮的起点索引 5000作为本轮专属标记天然携带了是哪一轮访问的这一信息恰好复刻了哈希表中 value 为起始点的语义。代码Python3class Solution: def circularArrayLoop(self, nums: List[int]) - bool: def can(cur, start, start_v): if nums[cur] 5000: return nums[cur] - 5000 start if nums[cur] ^ start_v 0: return False nxt ((cur nums[cur]) % n n ) % n if nxt cur: return False nums[cur] start 5000 return can(nxt, start, start_v) n len(nums) for i in range(n): if can(i, i, nums[i]): return True return False逐行理解这段代码if nums[cur] 5000当前节点已被标记落在值域外说明本轮或之前轮访问过它。nums[cur] - 5000 start判断它是否属于本轮是则说明本轮路径回到了自身标记的起点返回 true否则是历史轮的标记历史轮已证明经过该节点无环返回 false。一个判断同时覆盖两种情形if nums[cur] ^ start_v 0方向一致性检查start_v保存本轮起点的原始值用于比对符号if nxt cur: return False下一跳是自身即长度为 1 的自环直接剪枝——这是原地标记版需要显式处理的边界因为被标记的节点不能再作为后续判定的依据nums[cur] start 5000原地写入本轮专属标记后继续递归。复杂度分析令 n 为数组长度时间复杂度$O(n)$。每个节点至多被完整处理一次所有轮次的总访问次数是 O(n)空间复杂度不考虑递归产生的调用栈开销的话是 $O(1)$因为标记直接写在原数组上。原题解提示读者可以轻易将上述递归改写为迭代版本感兴趣的读者不妨动手尝试——迭代版本还能一并消除递归调用栈的 O(n) 空间做到严格意义的 O(1) 额外空间。三种解法对比解法核心思路时间复杂度额外空间复杂度备注解法一 暴力解每轮独立 visited DFS 探测$O(n^2)$$O(n)$最直观模板化适合快速 AC解法二 空间优化用steps n剪枝替代 visited$O(n^2)$$O(1)$不计栈省空间但常数更大不推荐解法三 原地标记数组值加 5000 映射为轮次标记$O(n)$$O(1)$不计栈满足进阶要求推荐掌握延伸思考快慢指针与迭代改写本题由于每个节点出度为 1与环形链表结构同构因此也可以联想到快慢指针Floyd 判圈的思路慢指针每次走一步、快指针每次走两步若两者相遇则存在环。但相比纯链表场景本题额外引入两个约束使用快慢指针时需要一并处理自环排除next(i) i的节点不构成合法循环需跳过方向一致性环上所有nums值必须同号快慢指针行进过程中需要持续校验符号这比解法三的先逐点探测稍显繁琐。这也是原题解最终选择逐起点 DFS 标记而非快慢指针的原因在同号 长度大于 1双重约束下标记法的实现更直接、边界更清晰。作为练习你可以尝试用快慢指针实现本题再与解法三对比两者的代码量与边界处理复杂度同时可以尝试把解法三改为迭代循环消除递归栈开销体会原地标记法从 O(n) 空间到严格 O(1) 空间的完整落地。仓库中的相关资源本题目解收录于 leetcode 仓库的 problems/457.circular-array-loop.md并登记在总目录 README.md 与 SUMMARY.md 的题目索引中。仓库还收录了同属环形数组 滑动窗口/状态统计思路的姊妹题 918. 环形子数组的最大和其核心同样是把环形数组展开为二倍长度线性化来处理可作为延伸练习进一步巩固对环形结构建模的理解。核心要点回顾本题的本质是在出度为 1 的有向图中检测长度大于 1 且方向一致的环。掌握三条主线即可通关——用((cur nums[cur]) % n n) % n统一处理环形越界、用异或判断同号、用值域外标记 轮次信息实现 O(n) 时间与 O(1) 空间的原地标记算法。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考