https://leetcode.com/problems/gas-station/

非常经典的一道题。解这道题的思路基于一个数学定理：

如果一个数组的总和非负，那么一定可以找到一个起始位置，从他开始绕数组一圈，累加和一直都是非负的

有了这个定理，判断到底是否存在这样的解非常容易，只需要把全部的油耗情况计算出来看看是否大于等于0即可。

那么如何求开始位置在哪？

注意到这样一个现象：

1. 假如从位置i开始，i+1，i+2…，一路开过来一路油箱都没有空。说明什么？说明从i到i+1，i+2，…肯定是正积累。
2. 现在突然发现开往位置j时油箱空了。这说明什么？说明从位置i开始没法走完全程(废话)。那么，我们要从位置i+1开始重新尝试吗？不需要！为什么？因为前面已经知道，位置i肯定是正积累，那么，如果从位置i+1开始走更加没法走完全程了，因为没有位置i的正积累了。同理，也不用从i+2，i+3，…开始尝试，这样就比暴力解法能省去很多时间。所以我们可以放心地从位置j+1开始尝试。
3. 每次油箱<=0的时候，要保存“欠下”的油量，当遍历完所有的i时，将当前余下的油减去所有之前欠下的油量，如果结果>=0才能说明能顺利跑完一轮。

# Brute Force, 遇到数组较大会超时报错。效率也很低。
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        start = 0   #起始位置
        remain = 0  #当前剩余燃料
        debt = 0    #前面没能走完的路上欠的债

        for i in range(len(gas)):
            remain += gas[i] - cost[i]
            if remain < 0:
                debt += remain
                start = i + 1
                remain = 0
        if remain + debt >= 0:
            return start
        else:
            return -1