There are N gas stations along a circular route, where the amount of gas at station i isgas[i].
You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
题意：N个气站围成一圈，在气站i有气gas[i]，从i到i+1要用掉气cost[i]，问能否环绕一圈
思路：走完整圈的前提条件是gas的总量要大于cost的总量。能从一个气站到下一个气站的条件是，之前多余的总气sum加上当前气站的总量要不小于当前的cost。这两点是要意识到的，其次，我们在想问题时，要将圆当做数组来想。
最关键的是，若从一个气站到下一个 气站不满足条件了，起始点的下标应该怎么计算？
若当前气站i不满足条件，起始点start的下标应从i+1开始，为什么？如：从下标为0开始，到下标为5不满足，为什么起始点下标不是从1开始，而是从6开始？因为，在当前下标之前每过一个气站之后sum都是大于等于0的（不然早就不满足了，为什么？sum小于0说明之前的消耗大于提供的），即气有剩余，当前站点之前的任意一个小的区间的sum都是小于当前这整段区间的sum，就这样到下标为5时，还是不满足，所以当前之前的任意下标都是不满足条件的。代码如下：
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
{
int sum=,start=,total=;
for(int i=;i<gas.size();++i)
{
sum+=gas[i]-cost[i];
total+=gas[i]-cost[i];
if(sum+gas[i]<cost[i]) //这里直接写sum<0也可以
{
start=i+;
sum=;
}
}
if(total<)
return -;
return start;
}
};参考了牛客网友的回答。