目标
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 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 可为起始索引。示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。说明:
- gas.length == n
- cost.length == n
- 1 <= n <= 10^5
- 0 <= gas[i], cost[i] <= 10^4
思路
一条环线上有 n 个加油站，加油站 i 有 gas[i] 升汽油，从加油站 i 到达加油站 i + 1 需要消耗汽油 cost[i] 升，假设有一辆油箱无限大的汽车，初始油箱为空，问从哪个加油站出发可以绕环线行驶一周，测试用例保证如果解存在则唯一，如果解不存在返回 -1。
枚举起点，模拟加油与耗油过程，记录剩余汽油，直到完成环线或者无法抵达下一加油站。值得注意的是，如果从起点 a 出发无法到达 b，那么从 (a, b) 之间的任意加油站出发都无法到达 b，因为到达下一站剩余的汽油是大于等于 0 的，如果带着剩余汽油都无法抵达，那么初始汽油为空更无法到达。我们可以将起点设为 b 继续枚举。
最开始写的是两次循环，后来又改成在一个while循环中，时间复杂度为 O(2n)。之所以是 2n 是因为 start 如果为 n - 1 那么需要再判断能否到达 0 ~ n - 1。
优化：如果 gasSum >= costSum， 那么解一定存在。注意到 remainder += gas[i] - cost[i] 其实就是在计算 gasSum - costSum，只是中间小于零的时候重置了，我们只需要一个变量 diff 将其保存起来，直接判断 diff 是否大于 0， 没必要再进行后续判断了。
代码
/**
* @date 2024-04-13 21:02
*/
public class CanCompleteCircuit134 {
public int canCompleteCircuit_v2(int[] gas, int[] cost) {
int n = gas.length;
int remainder = 0;
int start = 0;
int diff = 0;
for (int i = start; i < n; i++) {
remainder += gas[i] - cost[i];
if (remainder < 0) {
start = i + 1;
diff += remainder;
remainder = 0;
}
}
diff += remainder;
return diff < 0 ? -1 : start;
}
public int canCompleteCircuit_v1(int[] gas, int[] cost) {
int start = 0;
int cur = 0;
int n = gas.length;
int remainder = 0;
while (start < n) {
int i = cur % n;
remainder += gas[i] - cost[i];
if (remainder < 0) {
start = ++cur;
remainder = 0;
} else if ((i + 1) % n == start) {
return start;
} else {
cur++;
}
}
return -1;
}
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int remainder = 0;
int start = 0;
// 第一次循环，遇到断点就重新开始
for (int i = start; i < n; i++) {
remainder += gas[i] - cost[i];
if (remainder < 0) {
start = i + 1;
remainder = 0;
}
}
// 第二次循环，遇到断点说明不可达
for (int i = 0; i < start; i++) {
remainder += gas[i] - cost[i];
if (remainder < 0) {
return -1;
}
}
return start;
}
}
性能
两次循环
写成一次循环，实际上是循环了两个变量，并且循环中的操作也翻倍了
一次循环
