134. 加油站

思路

净油量(即从当前位置离开所剩余的油量）:gas[i]-cost[i]

cur：到达当前位置的净油量

total：到达当前位置的净油量和

start：起始位置，初始为0

到达当前位置total<0:说明油没了，无法去到下一位置了（因为离开当前位置需要的油多于现有的油），则起始位置从下一个位置开始

走到尾，若total<0,说明无法再往下走，走不到起始位置

假设起始位置前的净油量和为A，起始位置开始到末尾(-1这个位置）的净油量为B 即能回到起始位置需要总油量为A+B，即A+B>=0时，说明能回到起始位置（循环一圈）

class Solution(object):def canCompleteCircuit(self, gas, cost):""":type gas: List[int]:type cost: List[int]:rtype: int"""#到达当前位置的净油量cur=[]#到达当前位置的净油量和（即从这个位置离开时油量会是多少）total=0#起始位置start=0#到达当前位置的净油量和s=0for i in range(len(gas)):s+=gas[i]-cost[i]cur.append(s)total+=gas[i]-cost[i]'''从当前位置无法到下一个位置，油不够   因为是净油量  则起始到这个位置后，无法到达下一个位置那就以下一个位置为开始,重新计算油量'''if total<0:start=i+1total=0'''最后油量小于0，则回不到起始位置  因为一开始的地方0-start的前面油和（记为A）<0 ,走到底（从start到gas[-1]位置油和（记为B）也<0,）循环一遍，能走到起始位置条件为A+B>=0 即正好没油或多油 (存在解即唯一)'''if total+cur[start-1]>=0:return startreturn -1