8 ms c++ using accumulation sum


  • 4
    P
    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();
        }
    };

  • 0
    D

    @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 and cost arrays which have 2n elements each, but you don't seem to be doing that. An explanation would be great!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.