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.
这道题主要是数字分析，找规律。
首先，可以用gas[i]-cost[i]求得left[i]. 如何将所有的left[i]求和total<0，那么一定是不能循环一圈的。
如何total>0，那么一定是可以循环一圈的。就是要求这个起始点。
还有一点是，如果从i到j的和是负的，那么从i，j中间任意一个节点出发都是失败的。因为i到k是正的，i到j是负的，那么k到j一定是负的。
根据这个条件就可以得到一个O(n)的算法。
从i=0循环，如果求和为0，那么从i的下一个节点重新开始循环，直到index与i重合。
关键的一点是，i和index在最开始的时候会重合一次，最后还会重合一次。所以要用一个flag来标记是第几次重合。
1 public int canCompleteCircuit(int[] gas, int[] cost) { 2 int total = 0; 3 int[] left = new int[gas.length]; 4 for (int i=0; i<gas.length; i++) { 5 left[i] = gas[i] - cost[i]; 6 total += left[i]; 7 } 8 if (total < 0) return -1; 9 int s = 0; 10 int index = 0; 11 boolean flag = false; 12 for (int i=0; ; i = (i+1)%left.length) { 13 s += left[i]; 14 if (s < 0) { 15 s = 0; 16 index = (i+1)%left.length; 17 } 18 if (index == i) { 19 if (flag == false) 20 flag = true; 21 else 22 return index; 23 } 24 } 25 }
看到别人的方法，在我的基础上有一个新的观察，就是i只要循环到数组结尾就行。因为如果index到数组结尾是正的，那么它一定能循环回index。
反证法：假设从index到一个i<index的位置的和为负。因为index到结尾为正，那么从0到i一定是负的。同时从i到index一定是负的，否则不能以index起始。
所以三段加起来一定是负的。与total>0矛盾。
1 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { 2 int sum = 0; 3 int total = 0; 4 int j = -1; 5 for(int i = 0; i < gas.size() ; ++i){ 6 sum += gas[i]-cost[i]; 7 total += gas[i]-cost[i]; 8 if(sum < 0){ 9 j=i; sum = 0; 10 } 11 } 12 return total>=0? j+1 : -1; 13 }