class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
if(gas.empty()) return 1;
int min=gas[0]cost[0],sum=gas[0]cost[0],index=0;
/*compute the accumulation sum of gas[i]cost[i], when it takes minimum, the starting point should be the next station*/
for(int i=1;i<gas.size();i++){
sum += gas[i]cost[i];
if(sum<min){
min = sum;
index = i;
}
}
if(sum<0) return 1;
else return (index+1)%gas.size();
}
};
8 ms c++ using accumulation sum


@PKUGoodSpeed Please could you explain how/why this solution works (and is correct)? I'm surprised that you're not having to go through the elements twice in the worst case. i.e. The solution I implemented basically operates on the
gas
andcost
arrays which have2n
elements each, but you don't seem to be doing that. An explanation would be great!