Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[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.

The following solution reference the dicussion in leetcode.

Here we maintain two variable sum, total.

1.total is used to check whether the car can travel around the circuit.

2.sum is used to find the start index, when we find the sum is less than 0, it means that the last start index can not travel around the circuit,

we need to start from the next index. So the result should be startIndex + 1

只有一个答案，找到最后一个不可以的点，下一个是开始点

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

Gas Station

原文：http://www.cnblogs.com/RazerLu/p/3553603.html