[leetcode] gas station

先走一圈 算算 总油量是否大于等于耗油量，若不是的话 没有solution.

有的话 以i作为起点... 到j, 如若 sum[i..j] < 0 就是 i 不能到j... 立即将j+1作为起点...如此类推。
直到找到一个点k 到 结尾 n-1 能令sum[k..n-1] >= 0的

证明为什么这样可以成立的话.. 可以想象一个一个含有正数 负数的数列。。 这个数列的和既然>=0, 那么必然 正数和>=负数和...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { if (gas==null || cost == null||gas.length != cost.length){ return -1; } int sum = 0; for (int i = 0; i < gas.length; i++){ sum += (gas[i]-cost[i]); } if (sum < 0){ return -1; } int start = 0; sum = 0; for (int i = 0; i < gas.length; i++){ sum += gas[i]; sum -= cost[i]; if (sum < 0){ sum = 0; start = i+1; } } return start; } }