在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
如果题目有解，该答案即为唯一答案。输入数组均为非空数组，且长度相同。输入数组中的元素均为非负数。
首先汽车能环游一周的两个条件：
1.所有车站提供的油大于整个环游路程的消耗。
2.在某个站点时，当前油箱的油量加上该油站加的油后能达到下一个加油站。
对1，维护一个sum变量，记录油箱之和减去消耗之和，当达到最后一个站点sum>=0，则判断可以环游。
对2，维护一个cur变量，记录当前站点油箱的状态，如果小于0，说明无法到达下一个站点，重新更新起点start并置cur=0。
当某个站点i出现cur<0时，说明选取start到i中任意一个站点作为起点都无法到达i+1站点，因此重新改变start为i+1，在往后遍历。
当达到最后一个站点后，如果sum>=0说明可以环游一周。
但这只说明了从start(不一定是0)可以达到END站点，那从0能否到达start呢？
现在因为sum维护的是整个路程中的油箱状态，达到END sum>=0说明从0~END中油箱和是大于消耗和的。
假设在start前出现了两个断点n4,n7。
则由sum>=0可知start~END间的cur有盈余。而从假设起点为0时从0到n4中cur欠缺了x,然后新起点n4+1~n7间欠缺了y,实际上0~start间欠缺的就是x+y。
而由于sum>=0可知，start~END间的盈余一定是大于等于欠缺x+y的，否则sum将小于0
另外:在start~END，在END时是否会出现sum>=0而cur<0?
不会，因为start前一定是亏损的，而如果能环游一定要保证start~END间盈余，因此如果sum>=0则在start~END间一定是盈余的，有盈余才能弥补0~start间的亏损。
class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int sum=0; int cur=0; int start=0; for(int i=0;i<gas.size();i++) { int tmp=gas[i]-cost[i]; cur+=tmp; sum+=tmp; if(cur<0) { start=i+1; cur=0; } } if(sum<0) return -1; else return start; } };
转载于:https://www.cnblogs.com/lxy-xf/p/11149506.html
