环形数组是否存在循环
难度:
标签:
题目描述
存在一个不含 0 的 环形 数组 nums ，每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数：
- 如果
nums[i]是正数，向前（下标递增方向）移动|nums[i]|步 - 如果
nums[i]是负数，向后（下标递减方向）移动|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 。循环长度为 3 。
示例 2：
输入：nums = [-1,2] 输出：false 解释：按下标 1 -> 1 -> 1 ... 的运动无法构成循环，因为循环的长度为 1 。根据定义，循环的长度必须大于 1 。
示例 3:
输入：nums = [-2,1,-1,-2,-2] 输出：false 解释：按下标 1 -> 2 -> 1 -> ... 的运动无法构成循环，因为 nums[1] 是正数，而 nums[2] 是负数。 所有 nums[seq[j]] 应当不是全正就是全负。
提示：
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000nums[i] != 0
进阶：你能设计一个时间复杂度为 O(n) 且额外空间复杂度为 O(1) 的算法吗？
代码结果
运行时间: 23 ms, 内存: 16.1 MB
// Java Stream solution
// 思路：
// 1. 使用Stream API，处理数组元素。
// 2. 计算每个元素的移动方向和步数。
// 3. 利用Stream进行循环检测，返回结果。
// 由于Stream API在处理复杂逻辑时并不十分直观，因此这里示例代码主要展示Java流的简单使用。
import java.util.stream.IntStream;
public class StreamSolution {
public boolean circularArrayLoop(int[] nums) {
return IntStream.range(0, nums.length).anyMatch(i -> {
int slow = i, fast = i;
boolean isForward = nums[i] > 0;
while (true) {
slow = nextIndex(nums, slow, isForward);
fast = nextIndex(nums, fast, isForward);
if (fast != -1) {
fast = nextIndex(nums, fast, isForward);
}
if (slow == -1 || fast == -1 || slow == fast) break;
}
return slow != -1 && slow == fast;
});
}
private int nextIndex(int[] nums, int current, boolean isForward) {
if ((nums[current] > 0) != isForward) return -1;
int n = nums.length;
int next = ((current + nums[current]) % n + n) % n;
if (next == current) return -1;
return next;
}
}
解释
方法:
本题的解决方案采用了快慢指针的思想。通过快慢两个指针在环形数组中移动，如果存在循环，它们最终会相遇。同时，在移动过程中也要检查移动的方向是否一致，只有方向一致的情况下才可能形成循环。对于非循环的元素，将其标记为0，避免重复访问。最后，如果遍历完整个数组都没有发现循环，则返回 false。
时间复杂度:
O(n^2)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在检查快慢指针相遇时需要检查循环长度是否大于1？循环长度为1的情况具体是如何处理的？
▷🦆
在算法中，你是如何确保快慢指针在移动时始终保持方向一致的？
▷🦆
标记元素为0的策略是如何帮助提高算法效率的？是否存在可能误标记某些情况导致未能正确识别循环的风险？
▷🦆
算法中使用了`get_next_index`函数来处理环形数组的索引，能详细说明其计算逻辑和边界处理吗？
▷