0457. Circular Array Loop ========================= 题目信息 -------- :题号: 0457 :难度: Medium :主题: 环形数组、带符号步长、同向循环、循环长度 :原题: `LeetCode 0457 `_ :重点: 下标按数组长度循环、正数向右负数向左、循环内方向必须一致、单节点自环无效 题目重述 -------- 给定非零整数数组 ``nums``。从下标 ``i`` 出发,下一下标由 ``i + nums[i]`` 决定,并按数组长度循环回绕。正数表示向右移动,负数表示向左移动。 判断是否存在一个循环,使循环包含的下标数量大于 1,并且循环中所有移动方向一致:所有步长都为正,或所有步长都为负。长度为 1 的自环不算合法循环,即使某个步长回绕后仍落在自身。 ``nums.length`` 位于 ``[2, 5000]``,每个元素位于 ``[-1000, 1000]`` 且不为 0。函数只返回是否存在合法循环。 自建示例 -------- 整个数组形成正向循环: .. code-block:: text 输入:nums = [1, 1, 1] 输出:true 解释:下标按 0 -> 1 -> 2 -> 0 循环,长度为 3,且所有步长都为正。 循环路径混合方向: .. code-block:: text 输入:nums = [1, -1] 输出:false 解释:0 会走到 1,但下标 1 的步长为负,方向与前一步不同,因此不能构成合法同向循环。 限定方向的快慢指针 ------------------ 固定一个起点,先记录它的方向;沿路径移动时,若下一个位置的步长方向改变,当前路径立即失效。对仍保持同向的路径使用 Floyd 快慢指针:慢指针走一步、快指针走两步,若两者相遇且不是单节点自环,就发现了合法循环。 下标回绕用取模完成,负步长的余数需要加上 ``n`` 才能得到合法下标。每个起点都独立检查,因而不会把上一条路径的方向或循环误用于当前起点。 C++ 实现 -------- .. code-block:: cpp class Solution { int nextIndex(const std::vector& nums, int index) { int n = static_cast(nums.size()); long long next = (static_cast(index) + nums[index]) % n; if (next < 0) next += n; return static_cast(next); } public: bool circularArrayLoop(std::vector& nums) { int n = static_cast(nums.size()); for (int start = 0; start < n; ++start) { bool positive = nums[start] > 0; int slow = start; int fast = nextIndex(nums, start); while ((nums[slow] > 0) == positive && (nums[fast] > 0) == positive && (nums[nextIndex(nums, fast)] > 0) == positive) { if (slow == fast) { if (nextIndex(nums, slow) != slow) return true; break; } slow = nextIndex(nums, slow); fast = nextIndex(nums, nextIndex(nums, fast)); } } return false; } }; 代码分析 -------- 循环条件同时检查慢指针、快指针及快指针的下一步,保证相遇过程没有跨入相反方向的边。相遇后再排除 ``next(slow) == slow``,因此长度为 1 的自环不会被接受。该实现对每个起点最坏扫描 ``O(n)``,总时间复杂度为 ``O(n^2)``,额外空间复杂度为 ``O(1)``。