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

Categories:

题目描述
思路分析
1. 解法一：快慢指针 + 标记访问（推荐）
相似题目

题目描述

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

思路分析

解法一：快慢指针 + 标记访问（推荐）

核心思路：

对每个位置尝试以快慢指针检测环，要求方向一致且环长度大于 1。

每次判断 nums[i] 方向与起点方向不一致则停止。

为避免重复遍历，失败后将路径上的元素置为 0 标记已访问。

复杂度分析：

时间复杂度：O(n)，每个元素最多被清零一次。

空间复杂度：O(1)。

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
}

相似题目

题目	难度	考察点
142. 环形链表 II	中等	快慢指针
141. 环形链表	简单	快慢指针
287. 寻找重复数	中等	快慢指针
202. 快乐数	简单	快慢指针
2149. 按符号重排数组	中等	模拟

本文作者: HGNULB

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