# Gas Station

Suppose you are traveling along a circular route. On that route, we have N gas stations for you, where the amount of gas at station i is gas[i]. Suppose the size of the gas tank on your car is unlimited. To travel from station i to its next neighbor will cost you cost[i] of gas. Initially, your car has an empty tank, but you can begin your travel at any of the gas stations. Please return the smallest starting gas station's index if you can travel around the circuit once, otherwise return -1.

``````现在有4个加油站，汽油量gas[i]=[1, 1, 3, 1]，环路旅行时消耗的汽油量cost[i]=[2, 2, 1, 1]。则出发的加油站的编号为2。
``````

``````数据保证答案唯一。
``````

``````O(n)时间和O(1)额外空间
``````

## Solution

1. 从i开始，j是当前station的指针，sum += gas[j] – cost[j] （从j站加了油，再算上从i开始走到j剩的油，走到j+1站还能剩下多少油）
2. 如果sum < 0，说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢？既然i出发到i+1是可行的， 又i~j是不可行的， 从而发现i+1~ j是不可行的。
3. 以此类推i+2~j， i+3~j，i+4~j 。。。。等等都是不可行的
4. 所以一旦sum<0，index就赋成j + 1，sum归零。
5. 最后total表示能不能走一圈。

## Code

O(1)

``````public class Solution {
/**
* @param gas: an array of integers
* @param cost: an array of integers
* @return: an integer
*/
public int canCompleteCircuit(int[] gas, int[] cost) {
if (gas == null || cost == null || gas.length == 0 || cost.length == 0) {
// Bug 0: should not return false;
return -1;
}

int total = 0;
int sum = 0;

int startIndex = 0;

int len = gas.length;
for (int i = 0; i < len; i++) {
int dif = gas[i] - cost[i];
sum += dif;

if (sum < 0) {
// Means that from 0 to this gas station, none of them can be the solution.
startIndex = i + 1; // Begin from the next station.
sum = 0; // reset the sum.
}

total += dif;
}

if (total < 0) {
return -1;
}

return startIndex;
}
}
``````

O(n)

``````int canCompleteCircuit(int[] gas, int[] cost){
int len = gas.length;
if (len != cost.length || len == 0) return -1;

int[] arr = new int[len];
int sum = 0;
for (int i = 0; i < len; i++){
arr[i] = gas[i] - cost[i];
sum += arr[i];
}

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

sum = 0;
int index = 0;
for (int i = 0; i < len; i++){
sum += arr[i];
if (sum < 0){
sum = 0;
index = i + 1;
}
}
return index;
}

``````