Medium

题目描述

你正在玩一个涉及非零整数循环数组 nums 的游戏。每个 nums[i] 表示如果你在索引 i 处，必须向前/向后移动的索引数：

  • 如果 nums[i] 是正数，向前移动 nums[i] 步
  • 如果 nums[i] 是负数，向后移动 abs(nums[i]) 步

由于数组是循环的，你可以假设从最后一个元素向前移动会到达第一个元素，从第一个元素向后移动会到达最后一个元素。

数组中的循环包含长度为 k 的索引序列 seq，其中：

  • 遵循上述移动规则会产生重复的索引序列 seq[0] -> seq[1] -> ... -> seq[k-1] -> seq[0] -> ...
  • 每个 nums[seq[j]] 要么全为正数，要么全为负数
  • k > 1

如果 nums 中存在循环，返回 true；否则返回 false。

示例 1:

输入：nums = [2,-1,1,2,2]
输出：true
解释：存在循环 0 --> 2 --> 3 --> 0，所有节点都朝同一方向跳跃。

示例 2:

输入：nums = [-1,-2,-3,-4,-5,6]
输出：false
解释：唯一的循环大小为1，因此返回 false。

示例 3:

输入：nums = [1,-1,5,1,4]
输出：true
解释：存在循环 3 --> 4 --> 3，所有节点都朝同一方向跳跃。

约束条件:

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000
  • nums[i] != 0

进阶: 你能在 O(n) 时间复杂度和 O(1) 额外空间复杂度下解决这个问题吗？

解题思路

这道题需要检测循环数组中是否存在满足条件的循环。关键点在于理解循环的定义：必须是同方向且长度大于1。

解题思路

核心思想： 使用快慢指针检测循环，类似于检测链表中的环。

具体步骤：

  1. 对每个未访问的起始位置，使用快慢指针算法
  2. 慢指针每次移动一步，快指针每次移动两步
  3. 在移动过程中检查：
    • 是否形成自环（长度为1，不符合要求）
    • 方向是否一致（正负数不能混合）
    • 是否遇到相同位置（形成循环）

优化策略：

  • 使用标记避免重复访问已处理的节点
  • 当发现不满足条件的路径时，将路径上所有节点标记为已访问

关键函数：

  • getNext(): 根据当前位置和数组值计算下一个位置
  • isSameDirection(): 检查两个数是否同号

这种方法能够在O(n)时间内检测出所有可能的循环，通过合理的标记策略避免重复计算。

代码实现

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        
        auto getNext = [&](int i) -> int {
            return ((i + nums[i]) % n + n) % n;
        };
        
        auto isSameDirection = [](int a, int b) -> bool {
            return (a > 0) == (b > 0);
        };
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            
            int slow = i, fast = i;
            
            while (isSameDirection(nums[slow], nums[i]) && 
                   isSameDirection(nums[fast], nums[i]) && 
                   isSameDirection(nums[getNext(fast)], nums[i])) {
                
                slow = getNext(slow);
                fast = getNext(getNext(fast));
                
                if (slow == fast) {
                    if (slow == getNext(slow)) {
                        break;
                    }
                    return true;
                }
            }
            
            // 标记路径上的所有节点为已访问
            slow = i;
            int sign = nums[i];
            while (isSameDirection(nums[slow], sign)) {
                int next = getNext(slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        
        return false;
    }
};

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)
        
        def get_next(i):
            return (i + nums[i]) % n
        
        def is_same_direction(a, b):
            return (a > 0) == (b > 0)
        
        for i in range(n):
            if nums[i] == 0:
                continue
                
            slow = fast = i
            
            while (is_same_direction(nums[slow], nums[i]) and 
                   is_same_direction(nums[fast], nums[i]) and 
                   is_same_direction(nums[get_next(fast)], nums[i])):
                
                slow = get_next(slow)
                fast = get_next(get_next(fast))
                
                if slow == fast:
                    if slow == get_next(slow):
                        break
                    return True
            
            # 标记路径上的所有节点为已访问
            slow = i
            sign = nums[i]
            while is_same_direction(nums[slow], sign):
                next_pos = get_next(slow)
                nums[slow] = 0
                slow = next_pos
        
        return False

public class Solution {
    public bool CircularArrayLoop(int[] nums) {
        int n = nums.Length;
        
        int GetNext(int i) {
            return ((i + nums[i]) % n + n) % n;
        }
        
        bool IsSameDirection(int a, int b) {
            return (a > 0) == (b > 0);
        }
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            
            int slow = i, fast = i;
            
            while (IsSameDirection(nums[slow], nums[i]) && 
                   IsSameDirection(nums[fast], nums[i]) && 
                   IsSameDirection(nums[GetNext(fast)], nums[i])) {
                
                slow = GetNext(slow);
                fast = GetNext(GetNext(fast));
                
                if (slow == fast) {
                    if (slow == GetNext(slow)) {
                        break;
                    }
                    return true;
                }
            }
            
            // 标记路径上的所有节点为已访问
            slow = i;
            int sign = nums[i];
            while (IsSameDirection(nums[slow], sign)) {
                int next = GetNext(slow);
                nums[slow] = 0;
                slow = next;
            }
        }
        
        return false;
    }
}

var circularArrayLoop = function(nums) {
    const n = nums.length;
    
    const getNext = (i) => {
        return ((i + nums[i]) % n + n) % n;
    };
    
    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) continue;
        
        let slow = i, fast = i;
        let direction = nums[i] > 0;
        
        while (true) {
            slow = getNext(slow);
            if (nums[slow] === 0 || (nums[slow] > 0) !== direction || slow === getNext(slow)) {
                break;
            }
            
            fast = getNext(fast);
            if (nums[fast] === 0 || (nums[fast] > 0) !== direction || fast === getNext(fast)) {
                break;
            }
            
            fast = getNext(fast);
            if (nums[fast] === 0 || (nums[fast] > 0) !== direction || fast === getNext(fast)) {
                break;
            }
            
            if (slow === fast) {
                return true;
            }
        }
        
        let curr = i;
        while (nums[curr] !== 0 && (nums[curr] > 0) === direction) {
            let next = getNext(curr);
            nums[curr] = 0;
            curr = next;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多被访问常数次，通过标记避免重复访问
空间复杂度O(1)只使用常数额外空间，原地修改数组进行标记