134. Gas Station

greedy O(n)
能走完整个环的前提是gas的总量要大于cost的总量，这样才会有起点的存在。假设开始设置起点start = 0, 并从这里出发，如果当前的gas值大于cost值，就可以继续前进，此时到下一个站点，剩余的gas加上当前的gas再减去cost，看是否大于0，若大于0，则继续前进。当到达某一站点时，若这个值小于0了，则说明从0到这个点中间的任何一个点都不能作为起点，则把起点设为下一个点，继续遍历。当遍历完整个环时，当前保存的起点即为所求
证明用反证法，找total的反例

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, n = gas.size(), res = 0;
        for (int i = 0, sum = 0; i < n; ++i) {
            total += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (sum < 0) {
                res = i + 1;
                sum = 0;
            }
        }
        return total < 0 ? -1 : res;
    }
};

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    // write your code here
    const int n = gas.size();
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += (gas[i] - cost[i]);
    }
    if (sum < 0) { // sum < 0 means total gas < total cost, cannot complete
        return -1;
    }

    sum = 0;
    for (int i = 0; i < n;) {
        int j = i;
        for (; j < n; ++j) { // start from i
            sum += (gas[j] - cost[j]);
            if (sum < 0) {
                break;
            }
        }

        if (sum < 0) {
            sum = 0;
            i = j + 1;
        }
        else {
            return i;
        }
    }
}