CodeCollection2018
8/17/2019 - 7:38 AM

Gas Station循环加油站走回来的起始加油站

求出从哪一个油站开始，能够走完整个里程，并且这个结果唯一。 一开始是0，到一个加油站就加满油，从第i个加油站走到第i+1个加油站还要消耗一部分油，问从哪个加油站启动可以走回来。 分析：所有加油站的油量之和得大于消耗总量才能保证有一个加油站可以满足走回来得要求。如果到第i个加油站发现走不到第i+1个加油站了则答案不会在第i个及其之前得加油站，可以重新设定result=i+1然后继续走。

leetcode
content_copyfile_download
public int canCompleteCircuit(int [] gas,int [] cost){
    int sum = 0 ;
    int total = 0 ;
    int res = 0;
    for(int i = 0 ; i < gas.length;i++){
        sum += gas[i]-cost[i];
        if(sum < 0){
            sum=0;res=i+1;
        }
        total += gas[i]-cost[i];
    }
    return total>0?res:-1;
}