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

2021-05-12 HGNULB 约 6 分钟

文章信息 7 个分类 · 3 个标签

分类

LeetCode CodeTop 中等 未解决 2-5 微软 美团

标签

数组 哈希表 双指针

题目描述

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

题意分析

把每个下标看成一个节点，当前位置的元素值决定唯一的下一跳，越过首尾时循环取模。要找的环必须同时满足：环内步长全正或全负，且包含至少两个不同下标。

原数组不含零，但非零步长也可能恰好绕若干整圈回到自身。这种长度为 1 的环不符合要求。题目进阶要求线性时间、常数额外空间，下面用原数组中的零标记已排除的位置。

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

核心思路

[!blue]

从尚未清零的起点出发，固定本次方向 forward，把同号的下一跳关系当作链表。慢指针每轮走一步，快指针每轮走两步，并让快指针初始领先一步。快指针当前位置及下一步位置都必须非零且与起点同号；遇到已处理位置或方向变化，本次检测就结束。

若这条同方向路径含环，两个指针进入环后，每轮相对距离改变一步，最终一定相遇。相遇位置若下一跳还是自身，说明进入的是单点环，应排除；否则找到了同方向且长度大于 1 的合法环。

检测失败后，从原起点再走一遍，把沿途同方向节点清零。这样做不会漏解：每个节点的后继唯一，这段路径最终只会进入已被排除的路径、遇到反向节点，或落入单点环；从其中任何节点开始，也无法得到同方向合法环。清理必须在方向改变处停止，因为反方向节点可能属于另一条合法环。

清零前先保存下一跳，否则步长被改成零后就会停在原地。清零也兼作访问标记：如果清理路径本身闭合，绕回已经清零的位置就会停止。之后跳过这些起点，避免反复检测同一段失败路径。

解题步骤

• 下一跳先计算 step = nums[idx] % n，再计算 (idx + step) % n；结果为负时加上 n。
• 从非零起点开始检测，慢指针一步、快指针两步。
• 相遇且不是单点环时成功。
• 失败后先保存下一跳，再把当前元素清零，只清理本方向。

方向根据原步长的正负判断，不能根据跳转后下标是增大还是减小判断，因为环形越界会改变下标大小关系。只有一个元素时必然是单点环，流程自然返回 false。

代码实现

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)$。一次失败探测只在线性的同号路径上前进，随后这段路径被清零；每个位置最多被清零一次，不会再次作为未处理路径被完整检测。若发现合法环则立即返回。
• 空间复杂度：$O(1)$，清零标记复用输入数组。

关键点总结

[!green]

• 快慢指针负责判环，方向检查和单点环检查负责满足本题额外条件。
• 失败路径的后继唯一，才能将整段标记为无效并获得线性复杂度。
• 清零会修改输入数组；原输入不含零，因此这个标记不会与真实步长混淆。

易错点总结

[!yellow]

• 清零前没有保存下一跳，会丢失后续路径，无法完成剪枝。
• 清理越过符号变化，可能误删另一方向的合法环。
• 相遇即成功而不排除单点环，会接受整圈回到自己的位置。

相似题目

题目	难度	关联与区别
141. 环形链表	简单	普通快慢指针只需判断有环，本题还要求整环方向一致且长度大于1。
142. 环形链表 II	中等	同样把下标跳转视为next关系，本题要先处理模下标与方向限制，不能直接接受所有相遇。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/86348498

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！