## 457. Circular Array Loop 原

52iSilence7

#### Description

Difficulty : Medium

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be "forward" or "backward'.

Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.

Example 2: Given the array [-1, 2], there is no loop.

Note: The given array is guaranteed to contain no element "0".

Can you do it in O(n) time complexity and O(1) space complexity?

#### Solution

Points to be cared

1. A loop starts and ends at a particular index with more than 1 element along the loop. It means a satisfied loop contains more than 1 element
2. That the loop must be "forward" or "backward' means in a satisfied loop elements must be all postive or all negative

Mindpath:
Since the give array is guaranteed to contain no 0, we start from a index which is not zero then loop through the array.

Calculate next index and do next steps

1. check next index is zero or not, if it is, break
2. set next index element to zero. It means that we visited that element
3. check the direction, if changed, break
4. check whether next index is equal the initial index, if so, we find a loop

Code blow:

``````func circularArrayLoop(nums []int) bool {
size := len(nums)
if size <= 1 {
return false
}

for i:=0;i<size;i++{
if nums[i] == 0{
continue
}
direction := nums[i] > 0
curIndex := i
curVal := nums[i]
counter := 1
for true{
curIndex = curIndex + curVal
if curIndex >= size {
curIndex = curIndex - size
} else if curIndex < 0 {
curIndex = curIndex + size
}
curVal = nums[curIndex]
//traveled
if nums[curIndex] == 0 {
break
}
nums[curIndex] = 0
//loop detected
if curIndex == i &&  counter > 1{
return true
}
// direction changed
if !((direction && curVal >0) || (!direction && curVal < 0)){
break
}
counter++
}
}

return false
}
``````

### 52iSilence7

2018/01/05
0
0
jMyCarousel

JMyCarousel is a free, highly customizable, non obstrusive image carousel. It has been created to suit a maximum of needs. It enables to display a list or gallery of images in a......

2008/09/19
3.4K
0
Apache NiFi 1.7.1 发布，数据处理和分发系统

Apache NiFi 1.7.1 已发布，Apache NiFi 是一个易于使用、功能强大而且可靠的数据处理和分发系统。它为数据流设计，支持高度可配置的指示图的数据路由、转换和系统中介逻辑。 该版本有以下值...

2018/07/19
619
1

eeeneo
2012/07/23
0
0
FindBugs 3.0.1 RC1 发布，Java 代码 Bug 分析插件

FindBugs 3.0.1 RC1 发布，此版本更新内容如下： 新的 Bug 模式：CAA_COVARIANT_ARRAY_FIELD, CAA_COVARIANT_ARRAY_RETURN, CAA_COVARIANT_ARRAY_LOCAL, CAA_COVARIANT_ARRAY_ELEMENT_STORE......

oschina
2015/02/23
3.6K
1

node调用dll

Chason-洪

3
0
eclipse中项目svn转gitLab全过程

em_aaron

3
0
scala学习（一）

1
0

4
0

max佩恩

6
0