# 134 Gas Station

input: int[] gas 表示每個gas station供應的gas量，是一條circular route int[] cost 表示每個gas station到下一個gas station所需的gas

output: int index，回傳可繞此路線一圈的start station

Concept:

直覺想法是用暴力法，外層迴圈是假設每一個gas station當起點， 內層迴圈再跑過整條路線直到回到起點，看gas tank會不會變成負值， 若回到起點的過程中都沒有變負值，表示這個station可以當起點。 這樣寫的時間複雜度是O(n^2)，

但以這個input來看，應該有機會做到每個station只跑一遍就得到答案， 也就是O(n)的做法應該存在。

假設現在有條route: 1->2->3->4->5 以1為起點時: 1->2->3->4->5 以2為起點時: 2->3->4->5->1 以3為起點時: 3->4->5->1->2 以4為起點時: 4->5->1->2->3 以5為起點時: 5->1->2->3->4

以3為起點為例: 當我從1走到5時，1->2其實就是此路徑的後半， 只是先走了後半1->2，再走前半3->4->5， 因此可以用一個int index記錄起點，int total記錄起點前的(gas-cost)總和，tank記錄起點後的(gas-cost)總和。

Code:

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, tank = 0, index = 0;
        for (int i = 0; i < cost.length; i++) {
            int cur = gas[i] - cost[i];            

            tank += cur;
            if (tank < 0) {//if sum < 0, index can only start from i + 1
                index = i + 1;
                tank = 0;
            }
            total += cur;            
        }        
        return total < 0 ? -1 : index;
    }
}