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.
Note: The solution is guaranteed to be unique
沿环形路线有N个加油站，其中气体在车站i是量是gas[i]。你有车有无限容量的气罐，从加油站i到下一个加油站站点i+1，要消耗cost[i]的气体。你开始旅程时，气罐是空的。回到起始加油站的指数，选择一个起点开始旅游，如果你能在周围环形旅行一次，就返回开始的加油站索引，否则返回-1。 注意： 答案保证是唯一的。
首先先要明白：如果一个数组的总和非负，那么一定可以找到一个起始位置，从他开始绕数组一圈，累加和一直都是非负的。
如果从i出发，那么gas[i]-cost[i](dif[i])一定是大于0的，程序中有判断。如果dif[i]+dif[i+1]+……+dif[k-1]>=0，而dif[i]+dif[i+1]+……+dif[k-1]+dif[k]<0,此时需要重新设置开始点，那么需要从I+1开始吗？dif[i]肯定大于0，所有从i
+1开始，肯定不可能到达k点，少加了一个正数。那么需要设置开始点为K+1；
public int canCompleteCircuit(int[] gas, int[] cost) { // 记录访问的起始点 int start = 0; // 加的气和消耗的气的总差值(从0开始) int total = 0; // 从start位置开始，加的气和消耗的气的总差值 int sum = 0; for (int i = 0; i < gas.length; i++) { int dif = gas[i] - cost[i]; sum += dif; total += dif; // 走到i站是负数，说明走不到i站， // 也不能选取起始站到i站中的任何一战 if (sum < 0) { sum = 0; // 下一站作为起始点 start = i + 1; } } return total >= 0 ? start : -1; }
