LeetCode 457. 环形数组是否存在循环

2021-05-12 HGNULB 约 12 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 457. 环形数组是否存在循环

题意分析

数组首尾相接构成环，站在下标 i 时按 nums[i] 的值前进：正数向右走、负数向左走，走出边界就绕回来。问是否存在一个「合法循环」。

合法循环有两条附加条件，两条都不能省。第一，循环中所有元素的符号必须一致——要么全是正数（整圈顺时针），要么全是负数（整圈逆时针），不允许中途掉头。第二，循环长度必须大于 1，也就是说 nums[i] % n == 0 造成的原地自环不算数。

题目保证 nums[i] != 0，所以每一步都必然移动，不存在停在原地不动的情况；这也让 0 可以被安全地征用为「已访问」的标记值。

数组长度可达 5000，元素值范围是 int，绝对值可能远大于数组长度，所以计算下一个下标时必须先对 n 取模；而元素可为负，取模在多数语言里会得到负数，还要再补一次 n 才能落回合法下标。

题目还追问能否做到 $O(n)$ 时间、$O(1)$ 空间。这条追问排除了「用哈希集合记录访问过的下标」的做法，指向「在原数组上就地打标记」。

边界包括：数组长度为 1 时任何走法都是自环，答案必为假；全部元素同号且步长恰好整除 n 的情形；以及多条路径最终汇入同一个环的情形。

解法：快慢指针 + 标记访问

核心思路

把每个下标看成图上的一个点，从 i 到 next(i) 连一条有向边，则每个点恰好有一条出边。这样的函数图上，从任意点出发都必然走进一个环（因为点数有限而路径无限），所以「有没有环」不是问题，问题是「有没有满足符号一致且长度大于 1 的环」。

朴素做法是对每个起点走 n + 1 步看是否回到旧点，代价 $O(n^2)$，且要额外记录路径。瓶颈在于不同起点的路径大量重合——若干条路径最终会汇进同一个环，这个环被反复检测。

检测环本身用快慢指针：慢指针每次一步、快指针每次两步，若两者相遇则存在环，这不需要任何额外空间。相遇后再判一次 slow == next(slow)，就能排除长度为 1 的自环。

符号一致性用一个提前判定来处理：以起点的符号 forward 为基准，一旦路径上出现符号相反的元素就立刻放弃这条路径。这样做是正确的，因为环上任意一点的符号若与起点不同，这个环就不可能是「全同号」的；而如果环是全同号的，从起点走到环上的这段路径也必须全部同号，否则半路就断了。

关键的复杂度保证来自剪枝：一条路径检测失败后，把这条路径上所有与 forward 同号的元素全部置 0。这是安全的，因为从这些点出发的后续路径与刚才失败的路径完全重合（每个点只有一条出边），既然起点走不出合法环，它们也走不出来。置 0 之后，外层循环遇到它们会直接跳过。

不变量因此有两条。第一：值为 0 的下标已被证明「从它出发不存在合法循环」。第二：内层 while 循环执行期间，从起点到 fast 之间的所有元素都与 forward 同号且非零。

有了第一条不变量，每个元素至多被清零一次，所有路径的总步数被摊薄成线性，这正是 $O(n)$ 的来源。

解题步骤

写一个 next 辅助函数：先 nums[idx] % n 把步长压进一圈以内，再 (idx + step) % n，若结果为负则加 n。之所以先对步长取模，是因为 nums[idx] 可达 int 上界，直接相加会溢出；之所以要补 n，是因为负数取模在 Java 和 Go 里都保留负号，不补会得到非法下标。

外层循环遍历每个下标作为候选起点，遇到值为 0 的直接跳过。之所以能跳过，是第一条不变量的直接应用——这些点已被判定无解。

记录起点的符号 forward，初始化 slow = i、fast = next(i)。之所以让 fast 抢先一步，是为了让「相遇」这个事件能在环内被触发，而不是在起跑线上就误判为相遇。

内层 while 的条件包含四项：nums[fast] 非零、nums[next(fast)] 非零、nums[fast] 与 forward 同号、nums[next(fast)] 与 forward 同号。之所以要同时看 fast 和它的下一步，是因为快指针一轮要走两步，必须提前确认两步都落在合法区域内，否则会踩到已清零或反向的元素。

循环体内先判 slow == fast。若相等，再判 slow == next(slow)：成立说明这是长度为 1 的自环，break 放弃这条路径；否则说明找到了长度大于 1 且全程同号的环，返回真。之所以自环要单独排除，是因为快慢指针在自环上也会相遇，但题目明确要求循环长度大于 1。

未相遇则慢指针走一步、快指针走两步。之所以快慢比是 2 比 1，是因为这个速度差保证了两者的间距每轮恰好缩小 1，进环后必然在环长步内相遇。

内层循环结束（无论是条件不满足自然退出还是 break）后，从起点 i 开始沿路径把所有非零且与 forward 同号的元素置 0。之所以要先取 nxt 再赋值，是因为置 0 会破坏 nums[cur]，之后就再也算不出下一个下标了。

之所以清零循环的条件里要带符号判断，是因为路径可能走到一个反向元素上，那个元素属于别的方向的候选路径，不能被本次失败牵连清零。

外层循环走完仍未返回真，说明不存在合法循环，返回假。

以 nums = [2, -1, 1, 2, 2] 走一遍，n = 5，预期答案为真（下标 0 → 2 → 3 → 0 构成全正的长度 3 环）。

起点 i = 0：nums[0] = 2 > 0 所以 forward = true；slow = 0，fast = next(0) = (0 + 2) % 5 = 2。

第一轮判条件：nums[2] = 1 非零且为正；next(2) = (2 + 1) % 5 = 3，nums[3] = 2 非零且为正，四项全过。slow = 0 不等于 fast = 2。推进：slow = next(0) = 2；fast = next(next(2)) = next(3) = (3 + 2) % 5 = 0。

第二轮判条件：nums[0] = 2 非零为正；next(0) = 2，nums[2] = 1 非零为正，全过。此时 slow = 2、fast = 0，不等。推进：slow = next(2) = 3；fast = next(next(0)) = next(2) = 3。

第三轮判条件：nums[3] = 2 非零为正；next(3) = 0，nums[0] = 2 非零为正，全过。此时 slow = 3 等于 fast = 3，相遇。再判自环：next(3) = 0，不等于 3，说明环长大于 1。返回真，与预期一致。

再看一个失败并触发清零的例子：nums = [-1, 2]，n = 2，预期为假。起点 i = 0，forward = false，slow = 0，fast = next(0) = (0 - 1) % 2 = -1，补 2 得 1。判条件：nums[1] = 2 非零，但它是正数，与 forward = false 不符，条件失败，内层循环一次都不执行。随后清零：cur = 0，nums[0] = -1 非零且同号，取 nxt = 1，把 nums[0] 置 0，cur = 1；再判 nums[1] = 2 非零但符号不同，退出。此时数组是 [0, 2]。起点 i = 1：nums[1] = 2 非零，forward = true，fast = next(1) = (1 + 0) % 2 = 1（因为 2 % 2 = 0）。判条件：nums[1] 非零为正，next(1) = 1，nums[1] 非零为正，全过。slow = 1 等于 fast = 1，相遇；判自环：next(1) = 1 等于 slow，是自环，break。清零后数组变成 [0, 0]。外层结束返回假，正确。

代码实现

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                continue;
            }

            int slow = i;
            int fast = next(nums, i);
            boolean forward = nums[i] > 0;

            while (nums[fast] != 0 && nums[next(nums, fast)] != 0
                    && forward == (nums[fast] > 0)
                    && forward == (nums[next(nums, fast)] > 0)) {
                if (slow == fast) {
                    if (slow == next(nums, slow)) {
                        break;
                    }
                    return true;
                }

                slow = next(nums, slow);
                fast = next(nums, next(nums, fast));
            }

            int cur = i;
            while (nums[cur] != 0 && forward == (nums[cur] > 0)) {
                int nxt = next(nums, cur);
                nums[cur] = 0;
                cur = nxt;
            }
        }

        return false;
    }

    private int next(int[] nums, int idx) {
        int n = nums.length;
        int step = nums[idx] % n;
        int next = (idx + step) % n;
        if (next < 0) {
            next += n;
        }
        return next;
    }
}

func circularArrayLoop(nums []int) bool {
    n := len(nums)

    for i := 0; i < n; i++ {
        if nums[i] == 0 {
            continue
        }

        slow := i
        fast := nextIndex(nums, i)
        forward := nums[i] > 0

        for nums[fast] != 0 && nums[nextIndex(nums, fast)] != 0 &&
            forward == (nums[fast] > 0) && forward == (nums[nextIndex(nums, fast)] > 0) {
            if slow == fast {
                if slow == nextIndex(nums, slow) {
                    break
                }
                return true
            }

            slow = nextIndex(nums, slow)
            fast = nextIndex(nums, nextIndex(nums, fast))
        }

        cur := i
        for nums[cur] != 0 && forward == (nums[cur] > 0) {
            nxt := nextIndex(nums, cur)
            nums[cur] = 0
            cur = nxt
        }
    }

    return false
}

func nextIndex(nums []int, idx int) int {
    n := len(nums)
    step := nums[idx] % n
    next := (idx + step) % n
    if next < 0 {
        next += n
    }
    return next
}

复杂度分析

时间复杂度：$O(n)$，凭据是每个下标至多被清零一次，而清零之后外层循环会直接跳过、内层循环也会因 nums[x] != 0 失败而不再踏入；因此所有起点的探测步数总和被元素总数摊薄，均摊到每个元素是常数次访问。

空间复杂度：$O(1)$，凭据是标记「已访问」复用了原数组的 0 值而没有开辅助结构，环检测用的是快慢指针而非哈希集合，只额外维护了 slow、fast、cur、forward 几个变量。

关键点总结

「每个点恰好一条出边」的函数图上必然存在环，问题从「有没有环」变成「有没有满足附加条件的环」，识别出这一点就能把注意力全部放在条件校验上。

快慢指针是 $O(1)$ 空间的环检测标准工具；它的两个必备补丁是「相遇后再验一次自环」和「快指针每步都要预检两格的合法性」，缺任何一个都会出错。

附加条件（本题的符号一致）应当作为路径推进的前置门槛来实现，而不是等找到环之后再回头验证——前者天然保证了「路径与环都合规」，后者还要重新遍历环。

用原数组中不可能出现的值（本题保证 nums[i] != 0，于是 0 可用）就地打标记，是把 $O(n)$ 空间降到 $O(1)$ 的常用手法；使用前必须确认这个值确实不会与真实数据冲突。

失败路径整体清零的剪枝是复杂度的关键，它的正确性依赖「每个点出边唯一」这一结构性质：失败路径上任何点重启都会走同一条路。没有这条剪枝，复杂度会退回 $O(n^2)$。

就地修改数组前必须先把下一步位置算出来，因为修改会破坏计算所依赖的数据。

面试视角：面试官会先问朴素做法，再追问 $O(1)$ 空间。答题时要主动说出「用 0 打标记」和「失败路径整体清零」两个设计，并解释清零为什么安全。常见追问是「为什么长度为 1 的环要排除、怎么检测」，答案就是相遇后额外判一次 slow == next(slow)。

易错点总结

计算下一步写成 (idx + nums[idx]) % n：用例 nums = [2147483647, 1]，idx + nums[idx] 溢出成负数，取模后下标非法，抛数组越界异常；必须先对 nums[idx] 取模。

取模后不处理负数：用例 nums = [-1, 2]，(0 - 1) % 2 在 Java 和 Go 里都是 -1，直接用作下标会越界。

相遇后不判自环：用例 nums = [-1, -2, -3, -4, -5, 6] 中步长恰好整除 n 的位置，快慢指针在自环上必然相遇，会把长度为 1 的循环误判为合法，返回真而正确答案是假。

内层循环只检查 nums[fast] 而不检查 nums[next(fast)]：用例 nums = [-1, 2]，快指针一轮走两步，第二步可能落在符号相反或已清零的位置上，导致在非法区域内判定相遇。

符号判断用 nums[fast] * nums[i] > 0：用例 nums = [100000, 100000]，两个大正数相乘溢出成负数，同号被误判为异号，合法环被漏掉；应当分别取符号后比较布尔值。

失败后不清零：用例长度 5000 且构成一条长链最终汇入同一个环的数组，每个起点都要重走整条链，退化成 $O(n^2)$ 约 2500 万次访问，在大数据下超时。

清零时先赋值再算下一步，写成 nums[cur] = 0; cur = next(nums, cur);：用例任意需要清零的路径，next 读到的是已经被置 0 的步长，永远原地不动，陷入死循环。

清零循环不带符号判断，写成 while (nums[cur] != 0)：用例 nums = [-1, 2]，起点 0 失败后会连带把属于正方向候选的 nums[1] 也清掉，如果 nums[1] 本可以构成合法环就会被漏判。

初始化 fast = i 而不是 next(i)：用例任意输入，第一轮 slow == fast 立刻成立，slow 又不等于 next(slow) 时直接返回真，任何数组都被误判为有环。

用 HashSet 记录访问过的下标来判环：用例长度 5000 的数组，答案正确但空间是 $O(n)$，不满足题目追问的常数空间要求，面试中会被要求重写。

认为符号一致只需检查环上元素、路径上可以混杂：用例起点为负数但走两步后进入全正环的数组，若不在推进时就拦截，会把「起点方向与环方向不同」的情形错误接受；本题的判定必须以起点符号为准全程贯彻。

相似题目

题目	难度	考察点
141. 环形链表	简单	最纯粹的快慢指针判环，无附加条件也无需就地标记
142. 环形链表 II	中等	要求返回环的入口，需要在相遇后从头再走一轮的数学推导
287. 寻找重复数	中等	把数组下标映射成链表边后找环入口，考察建模而非判环本身
202. 快乐数	简单	状态由数位平方和生成，环检测用于判断是否陷入非 1 循环
207. 课程表	中等	出边不唯一的一般有向图判环，只能用拓扑排序或三色标记