leetcode134. gas station

One : The analects of Confucius

Two ： subject

3、 ... and ： Upper code ( Violent solution time out But method two is OK )

// class Solution {
    
// public:
// int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    
// /**
//  Ideas :1. Violence solution , We traverse all elements   Until you can succeed   Otherwise return to -1;
// */
// for(int i = 0; i < gas.size(); i++) {
    
// int num1 = gas[i] - cost[i];
// int index = (i+1) % cost.size();// Here we use this to realize our cycle  index Represents array subscript 

// while(num1 > 0 && index != i) {
    
// num1 += gas[index] - cost[index];
// index = (index+1) % cost.size();// When index+1 == cost.size() When   We're back 0 The starting point 
// }
            
// if(num1 >= 0 && index == i) return i;
// }

// return -1;
// }
// };

class Solution {
    
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    
        /**  Ideas :1. If our total oil volume is greater than the oil consumption   We can definitely go around  */
        int cur = 0;
        int sum = 0;
        int start = 0;

        for(int i = 0; i < gas.size(); i++) {
    
            cur += gas[i] -cost[i];
            sum += gas[i] -cost[i];
            
            if(cur < 0) {
    // When we count  i  When   If the fuel quantity is negative , We can be sure that we won't go around 
                start = i+1;
                cur = 0;
            }
        }   

        if(sum < 0) return -1;
        return start;
    }
};