你知道的，失败总是贯穿人生的始终。
加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
思路分析
这题其实就像是一个“环球旅行”的游戏。想象你有一辆油箱可以无限装油的车，你要开着这辆车从某个加油站出发，沿着一条环形的路线旅行一圈再回到出发的那个加油站。每个加油站都有一定数量的汽油可以加到你的车里，而从一个加油站到下一个加油站的路途中，你的车会消耗一定的汽油。
具体来说，题目提供了两个数组：
-
gas 数组：表示每个加油站能给你的车加多少升的油。例如 gas[i] 表示在第 i 个加油站可以加 gas[i] 升油。
-
cost 数组：表示从一个加油站开到下一个加油站需要消耗多少升的油。例如 cost[i] 表示从第 i 个加油站开到第 i+1 个加油站需要消耗 cost[i] 升油。由于这是一个环形路线，所以从最后一个加油站回到第一个加油站也会消耗一定的油。
你的任务是找出一个起点加油站的编号，从这个起点加油出发，使用上面提供的油量和消耗量，你可以成功地绕行一圈回到这个起点，而不会在中途因为油不够而停下来。如果找不到这样的起点，就返回 -1。注意，题目保证如果有解，这个解是唯一的。
如何理解余量数组？
首先拿每个gas[i]减去cost[i],得到余量数组，也就是说，加的油减去耗去的油，如果结果是小于0的，那么说明这个点是不能转一圈的。
如何理解转圈?
对于余量数组如下图而言，拿0下标举例，从0->1->2->3->4->5->0,就是转圈
-
1->2->3->4->5->0->1 是转圈
-
2->3->4->5->0->1->2 是转圈
-
...依次类推
代码中是如何处理转圈的呢？
想象着把数组copy了一份，然后每一个转圈就被铺平了，比如从2号下标开始，对应的就是2-8(8%6)号下标。这样就不用两个for循环处理了，时间复杂度O(n)
如何得到结果
把每个余量数组的值加起来，如果前缀和都大于0，那么代表可以转圈。有一个小于0，就不能转圈。返回最早那个可以转圈的下标，其实所有的点都可以判断，但是本题是要求返回满足转圈条件最早的那个。
对于余量数组[3,5,-10,6,7,-4]而言
-
从0号下标开始累加，【3+5+（-10）】<0 ，pass掉
-
从1号下标开始，5+（-10）<0,pass
-
从2号下标开始,-10本身小于0，pass
-
从3号下标开始，6+7=13，13-4=9，9+3=12，12+5=17，17-10=7，7+6=13，我们可以发现，每一个加法得出的结果都是大于等于0的，返回3
如何优化
有两个点
第一点，在处理转圈的时候，我们把环转为一个直线处理
第二点，在挨个判断余量数组的时候可以跳跃。
对于余量数组[3,5,-10,6,7,-4]而言，原来得挨个判断
-
从0号下标开始累加，【3+5+（-10）】<0 ，pass掉
-
从1号下标开始，5+（-10）<0,pass （多余）
-
从2号下标开始,-10本身小于0，pass
-
从3号下标开始，6+7=13，13-4=9，9+3=12，12+5=17，17-10=7，7+6=13，我们可以发现，每一个加法得出的结果都是大于等于0的，返回3
其实在3+5=8，8+-10=-2时，1号下标是不用判断的。1号下标的判断是多余的，直接跳到2号下标开始判断。抽象化就是从l--r-1开始的累加和都大于0，但是加到r时，累加和<0,l-r-1的下标都不用判断了，l直接跳到r开始继续判断。
也就是对应以下代码，左边界有一个跳跃,l=r+1,r=l;
完整代码
// 加油站
// 在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
// 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
// 你从其中的一个加油站出发，开始时油箱为空。
// 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周
// 则返回出发时加油站的编号，否则返回 -1
// 如果存在解，则 保证 它是 唯一 的。
// 测试链接 : https://leetcode.cn/problems/gas-station/
public class Code04_GasStation {public static int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length;// 本来下标是0..n-1，但是扩充到0..2*n-1，i位置的余量信息在(r%n)位置// 窗口范围是[l, r)，左闭右开，也就是说窗口是[l..r-1]，r是到不了的位置for (int l = 0, r = 0, sum; l < n; l = r + 1, r = l) {sum = 0;while (sum + gas[r % n] - cost[r % n] >= 0) {// r位置即将右扩，窗口会变大if (r - l + 1 == n) { // 此时检查是否已经转了一圈return l;}// r位置进入窗口，累加和加上r位置的余量sum += gas[r % n] - cost[r % n];// r右扩，窗口变大了r++;}}return -1;}}
