Array: Gas Station

有一个环形公路上有n个加油站，第i个加油站的油量为a_i。假设有一辆邮箱体积无穷大的汽车，初始邮箱是空的，汽车从加油站i行驶到加油站i+1需耗油g[i]。

问是否能够选出某个加油站作为起点，使汽车能够绕环形公路行驶一圈返回到该加油站。

实现函数int selectGasStation(int a[], int g[], int n)，如果存在满足条件的加油站，返回该加油站的序号(0-based)。否则返回-1。

提示：n可能达到10⁶，O(n²)的枚举算法会超出时间限制。

public class SelectGasStation { public int selectGasStation(int[] a, int[] g) { int want = 0, has = 0, diff = 0, r = 0; for(int i = 0 ; i < a.length ; i++){ want +=g[i]; has += a[i]; diff += a[i] - g[i]; if(diff < 0){ diff = 0 ; r = i +1; } } if(want > has) return -1; else return r; } }

public class Solution { /** * @param gas: an array of integers * @param cost: an array of integers * @return: an integer */ public int canCompleteCircuit(int[] gas, int[] cost) { // write your code here if(gas==null || gas.length==0 || cost==null || cost.length==0 || gas.length!=cost.length) return -1; int sum = 0; int total = 0; int pointer = -1; for(int i=0;i<gas.length;i++) { int diff = gas[i]-cost[i]; sum += diff; total += diff; if(sum<0) { sum=0; pointer=i; } } return total>=0?pointer+1:-1; } }