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.
| gas[0] | gas[1] | gas[2] | gas[3] |
| cost[0] | cost[1] | cost[2] | cost[3] |
| remain[0] | remain[1] | remain[2] | remain[3] |
1 class Solution { 2 public: 3 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { 4 vector<int> remain(gas.size(), 0); 5 for(int i=0; i<remain.size(); ++i) 6 remain[i] = gas[i]-cost[i]; 7 int start = 0; 8 int sum = 0; 9 int total = 0; //统计整个remian的和 10 for(int i=0; i<remain.size(); ++i) { 11 total += remain[i]; 12 sum += remain[i]; 13 if( sum < 0 ) { //如果sum为0，表明前面的连续子序列和为负数，需要重新另选起点 14 start = i+1; 15 sum = 0; 16 } 17 } 18 return ( (total < 0) ? -1 : start ); //若total为负数，说明不可能完成 19 } 20 };
原文：http://www.cnblogs.com/bugfly/p/3923032.html