题设
    在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
    你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

    如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

    说明:

    如果题目有解，该答案即为唯一答案。
    输入数组均为非空数组，且长度相同。
    输入数组中的元素均为非负数。

    示例 1:
    输入:
    gas = [1,2,3,4,5]
    cost = [3,4,5,1,2]
    输出: 3

    解法1
    分析
    根据题设我们只需要从0到4 遍历一遍数组，然后判断以这中间的每个位置作为起始位置能否循环一周，只要存在能循环一周的起始位置，那么该位置下标就能作为结果返回。既然每个下标位置作为起始位置是一样的，那么只要分析循环中单次执行的时候什么时候判断能行驶一周，什么时候不能就可以了。

    单次循环判断

    位置:0 1 2 3 4
    油站:1 -> 2 -> 3 -> 4 -> 5
    油耗:3 -> 4 -> 5 -> 1 -> 2

    从下表0,1,2 开始行驶 , 很显然的，在当前起始位置的时候就出现了 油量 < 油耗 , 所以肯定不能循环一周。 当从下标 3 开始时 ， 3 -> 4 剩余油量为 4-1 = 3， 4 -> 0 剩余油量为 3 + 5-2 = 6， 0 ->1 剩余油量为 6+1-3= 4, 1->2 剩余油量为 4 + 2 - 4 = 2， 2 ->3 剩余油量为 2+3 - 5 = 0 。走到位置3的时候汽车已经行驶一周了，这说明3这个位置开始可以绕环路行驶一周。

    一般化而言，对于所有从下标i开始的情况，只要汽车能够再次行驶到 i%len 就说明能行驶一周，这里之所以对len求模是因为对于 i = len -1 的情况，需要再次行驶到 len-1。

    实现

    1.     public int canCompleteCircuit(int[] gas, int[] cost) {
    2.         int len = gas.length;
    3.         for(int i = 0 ; i < gas.length ; i++){
    4.             int k = i, totalGas = 0;
    5.             while(totalGas >= 0){
    6.                 totalGas += gas[k] - cost[k];
    7.                 k = (k+1) % len;
    8.                 if(k == i && totalGas >= 0){
    9.                     return i;
    10.                 }
    11.             }
    12.         }
    13.         return -1;
    14.     }

    解法2**
    分析
    上述暴力破解法确实容易想到和实现，但是时间复杂度会高达 O(n) 那么就还有优化简化实现的必要。

    回看上面的解法，代码行totalGas += gas[k] - cost[k]; 发现本质上而言能否行驶到下一个站的判断其实是看当前剩余油量 加上 位置k 的可加油量 能否大于 位置k需要消耗的油量。那么走完一圈总共消耗的油 totalCost <= totalGas 时才有可能走完一圈，否则可以设想在某个位置汽车里面的剩余油量 + gas[k] - cost[k] 势必会小于 0。

    那在满足 totalGas >= totalCost 的情况下，如何判断某个位置 i 开始行驶能够行驶一周呢？以及totalGas >= totalCost 时就一定能绕环形加油站行驶一周呢？

    考虑常见的油量不够的情况：
    假设从 i 位置开始行驶到 j 时发现油量不够了，那么对于
    (1) i==j 这时相当于一站都还没经过
    (2) i < j 那么可以得出以下结论:

    ① gas[i] + gas[i+1] + … + gas[j-1] > cost [i] + cost [i+1] + … + cost [j-1] ② gas[i] + gas[i+1] + … + gas[j] < cost [i] + cost [i+1] + … + cost [j]

    此外位置 i 作为起始位置 必然有 gas[i] >= cost[i]，相当于位置 i 为油箱剩余了 gas[i] - cost[i] 的油量，

    那么如果将从i 到 j-1 分分步骤来看的话，剩余油量就具有如下的关系

    i -> i+1 : left = gas[i] -cost[i] >= 0 i+1 -> i + 2 : left = left + gas[i+1] - cost[i+1] >= 0 …… i+2 -> j-1 : left = left + gas[j-2] - cost[j-2] >= 0 j-1 -> j : left = left + gas[j-1] - cost[j-1] >= 0


    可以看到在到达 位置 j 前，行走的每一步都是有上一步的剩余油量的贡献的，而且上一步贡献度的剩余油量一定会大于等于 0 ，这是因为上一步要走完的话油量至少是刚刚好的情况 也就是 left = 0。

    那么如果这次在位置 j 因为发现油量不够而不能行驶到 位置 j+1时，假设我们 下一次以 i+1 作为行驶的起始位置，就会发现依然还是会在位置 j 那里在到达j+1 之前把油量耗尽，因为这次从 i+1 开始，我们在行驶相同的路线时缺少了 gas[i] - cost[i] 这部分剩余油量的贡献，显然只会更加走不下去。

    从事上述剩余油量的关系 来看， 我们选取从 i+2，… ，j-1 都会有同样的结果， 而对于位置j 显然的有 gas[j] < cost[j] 那就更加不用说了，因此在选择下一个起始位置时区间[i,j] 范围内的位置都可以跳过，直接从j+1 的位置开始判断。

    到这里，我们发现了一个规律，对于全局范围[0,len-1] 的判断，只要分中途出现了油量不够的情况，我们都可以分区间的判断。现假设行驶完 [0,len-1] ，总共分了 k 个区间： 前 k-1 个区间都出现了区间末尾油量不够的情况。那么有：

    [0 , i1] : Σcost - Σgas = n [i1 , i2] : Σcost - Σgas = n2 …… [ik-2 , ik-1] : Σcost - Σgas = nk-1 [ik , len-1] : Σgas - Σcost = nk

    前 k-1 个区间都存在都油量不够的问题，那么在那些区间内 Σcost - Σgas 一定是大于 0的，由于总油量 >= 总消耗量。对于 这k个区间而言， 就有 nk > n + n2 + … + nk-1 ， 也就是说在最后一个区间走完后会剩余 不少于 之前所有区间缺少的油量的总和。这就回答了上述提及的这个问题:

    如何判断某个位置 i 开始行驶能够行驶一周呢？totalGas >= totalCost 时就一定能绕环形加油站行驶一周呢？

    结论是:

    • totalGas >= totalCost 时一定能绕环形加油站行驶一周
    • totalGas >= totalCost 时哪个下标开始行驶后能行驶到最后下标，以下标开始就能行驶一周


    实现**

    1.     public int canCompleteCircuit(int[] gas, int[] cost) {
    2.         int gasLeft = 0;
    3.         int len = gas.length;
    4.         for(int i = 0 ; i < len ; i++){
    5.             gasLeft += (gas[i] - cost[i]);
    6.         }
    7.         if(gasLeft < 0) return -1;
    8.         int totalGas = 0,st = 0;
    9.         for(int k = 0; k < len ; k++){
    10.             totalGas += (gas[k] - cost[k]);
    11.             if(totalGas < 0){
    12.                 totalGas = 0;
    13.                 st = k+1;
    14.             }
    15.         }
    16.         return st < len ? st : -1;
    17.     }