---恢复内容开始---

这道题考察的可能偏向逻辑的思考能力。

最有效的方法是时间复杂度为O(n)，空间复杂度为O(1).这种高效算法，参考一个前辈的思想：“My linear solution based on a observation that, if you stops at certain gas station, the gas stations previous to the station you stop must not be a valid starting point. ”

意思是说从某个station开始，如果不能回到这个station，而是停在中间某一个station，那么从start到stop的这些station都不能作为汽车的起点。

下面是AC代码：

/**     *      * @param gas     * @param cost     * @return Return the starting gas station's index if you can travel around     *  the circuit once, otherwise return -1.     */    public int canCompleteCircuit(int[] gas, int[] cost)    {        int left = 0;        int start=0, i;        int N = gas.length;        while(true)        {            i = start;            left = 0;            while(left+gas[i%N]-cost[i%N]>=0)            {                left = left+gas[i%N]-cost[i%N];                i++;                if(i%N == start%N)                    return i%N;            }            if(i>N-1)                return -1;            start = ++i;            }    }

 

---恢复内容结束---