134. 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.

Brutal way O(n^2) ,计算每一个点，做一边sum gas and cost 会超时tle

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int step = gas.length;
        int start = 0;
        for(int i = 0; i < step; i++){
          int temp = start;
          int station = 0;
          int sumGas = 0;
          int sumCost = 0;
          while(sumCost <= sumGas && station < step){
            sumGas += gas[start%step];
            sumCost += cost[start%step];
            start ++;
            station ++;
          } 
          if(station >= step && sumGas >= sumCost) return temp;
          else if(station < step) start = temp + 1;
        }
        return -1;
    }
}

最优解：

设一个total ＝ sum （gas[i] - cost[i]）

if(total < 0) return -1

if(total > 0) 一定存在一个解；

用sum ＝ gas[i] + cost[i]

if(sum < 0)  i - > i+1 sum要重新算

if(sum > 0)  sum 累加

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int sum = 0;
        int start = 0;
        for(int i = 0; i < gas.length; i++){
            total += gas[i] - cost[i];
        }
        if(total < 0)
            return -1;
            
        for(int i = 0; i < gas.length; i++){
            if(sum >= 0){
                sum += gas[i] - cost[i];
            }
            else{
                sum = gas[i] - cost[i];
                start = i; //记录新的起点
            }
        }
        return start;
    }
}