134. Gas Station 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func canCompleteCircuit(gas []int, cost []int) int {
    for i := 0; i < len(gas); {
        // 尝试用 i 作为起点，如果能走 gas.length 步，说明能环路行驶一周
        j, steps, left := i, 0, 0
        for steps < len(gas) {
            if left+gas[j]-cost[j] >= 0 {
                left += gas[j] - cost[j]
                steps++
                j = getNextIndex(j, len(gas))
            } else {
                break
            }
        }

        if steps == len(gas) {
            return i
        } else {
            i += steps + 1 // 注意此处不进行取余，因为起点只需遍历一次
        }
    }

    return -1
}

func getNextIndex(j int, length int) int {
    return (j + 1) % length
}

References

134. Gas Station