0457. Circular Array Loop

# 457. Circular Array Loop#

## 题目 #

You are given a circular array `nums` of positive and negative integers. If a number k at an index is positive, then move forward k steps. Conversely, if it’s negative (-k), move backward k steps. Since the array is circular, you may assume that the last element’s next element is the first element, and the first element’s previous element is the last element.

Determine if there is a loop (or a cycle) in `nums`. A cycle must start and end at the same index and the cycle’s length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

Example 1:

``````Input: [2,-1,1,2,2]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.
``````

Example 2:

``````Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.
``````

Example 3:

``````Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.
``````

Note:

1. -1000 ≤ nums[i] ≤ 1000
2. nums[i] ≠ 0
3. 1 ≤ nums.length ≤ 5000

Could you solve it in O(n) time complexity and O(1) extra space complexity?

## 题目大意 #

• -1000 ≤ nums[i] ≤ 1000
• nums[i] ≠ 0
• 1 ≤ nums.length ≤ 5000

• 你能写出时间时间复杂度为 O(n) 和额外空间复杂度为 O(1) 的算法吗？

## 解题思路 #

• 给出一个循环数组，数组的数字代表了前进和后退的步数，+ 代表往右(前进)，- 代表往左(后退)。问这个循环数组中是否存在一个循环，并且这个循环内不能只有一个元素，循环的方向都必须是同方向的。
• 遇到循环就可以优先考虑用快慢指针的方法判断循环，这一题对循环增加了一个条件，循环不能只是单元素的循环，所以在快慢指针中加入这个判断条件。还有一个判断条件是循环的方向必须是同向的，这个简单，用 `num[i] * num[j] > 0` 就可以判断出是同向的(如果是反向的，那么两者的乘积必然是负数)，如果没有找到循环，可以将当前已经走过的路径上的 num[] 值都置为 0，标记已经访问过了。下次循环遇到访问过的元素，`num[i] * num[j] > 0` 就会是 0，提前退出找循环的过程。

## 代码 #

``````
package leetcode

func circularArrayLoop(nums []int) bool {
if len(nums) == 0 {
return false
}
for i := 0; i < len(nums); i++ {
if nums[i] == 0 {
continue
}
// slow/fast pointer
slow, fast, val := i, getNextIndex(nums, i), 0
for nums[fast]*nums[i] > 0 && nums[getNextIndex(nums, fast)]*nums[i] > 0 {
if slow == fast {
// check for loop with only one element
if slow == getNextIndex(nums, slow) {
break
}
return true
}
slow = getNextIndex(nums, slow)
fast = getNextIndex(nums, getNextIndex(nums, fast))
}
// loop not found, set all element along the way to 0
slow, val = i, nums[i]
for nums[slow]*val > 0 {
next := getNextIndex(nums, slow)
nums[slow] = 0
slow = next
}
}
return false
}

func getNextIndex(nums []int, index int) int {
return ((nums[index]+index)%len(nums) + len(nums)) % len(nums)
}

``````

Nov 25, 2022