Leetcode - 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.
[分析] 这道题目暴力法是容易的，但是O（n）的解法都不是那么容易理解的，下面是转载https://leetcodenotes.wordpress.com/2013/11/21/leetcode-gas-station-%E8%BD%AC%E5%9C%88%E7%9A%84%E5%8A%A0%E6%B2%B9%E7%AB%99%E7%9C%8B%E8%83%BD%E4%B8%8D%E8%83%BD%E8%B5%B0%E4%B8%80%E5%9C%88/的思路：
用反证法来理解。算法：
从i开始，j是当前station的指针，sum += gas[j] – cost[j] （从j站加了油，再算上从i开始走到j剩的油，走到j+1站还能剩下多少油）
如果sum < 0，说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢？假设能从k (i <=k<=j)走，那么i..j < 0，若k..j >=0，说明i..k – 1更是<0，那从k处就早该断开了，根本轮不到j。所以一旦sum<0，i就赋成j + 1，sum归零。最后total 表示能不能走一圈。
看完这个思路后我还有一点疑惑是貌似sum仅计算了[i..N -1]这段能否走下来，为啥total非负就能确定从i 开始可以走完一圈？ 对于这个疑惑同样可以用反证法证明（怀疑别人结论时就尝试举反例试试~）：
[p, q]表示汽车从p 站出发到达q + 1站时的剩油量。记A=[i, N-1], B=[i, k-1], C=[i, i-1]，D=[0, k - 1], E=[k, i - 1], 假设A >= 0 && total >= 0时，B < 0。 因为total == A + D + E, 而（B == A + D）< 0, 则E > 0。 A >= 0, 那么E + A >0，因此按算法找到的start 就不会是 i 而是 k。

[ref]
http://blog.csdn.net/linhuanmars/article/details/22706553
http://blog.csdn.net/kenden23/article/details/14106137

public class Solution {
    // Method 2: O(n)
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || cost == null || gas.length != cost.length)
            return -1;
        int N = gas.length;
        int start = 0;
        int sum = 0, total = 0;
        for (int i = 0; i < N; i++) {
            total += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (sum < 0) {
                start = i + 1;
                sum = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
    // Method 1: O(n^2), time out
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        if (gas == null || cost == null || gas.length != cost.length)
            return -1;
        int N = gas.length;
        for (int i = 0; i < N; i++) {
            int volume = 0, j = 0;
            for (; j < N; j++) {
                int curr = (i + j) % N;
                volume += gas[curr];
                volume -= cost[curr];
                if (volume < 0)
                    break;
            }
            if (j == N)
                return i;
        }
        return -1;
    }
}