LeetCode题解：加油站

题目描述

在一条环路上有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 可为起始索引。

方法思路

i=i+cnt+1的解释：如果x到不了y+1（能到y），那么从x到y的任意一点出发都不可能到达y+1。因为从上一个点能到下一个点就说明扣除耗油量cost[i]还有富余（至少也为0），但是在x与y之间每少一个点意味着到达y之前的富余油量在减少（极端情况下，也就是这中间的gas值与cost值相同，富余油量减少值为0）。所以当内部循环while（cnt<n）出一次循环但还为出结果时，就必须跳过这中间的点，因为这之间的点无法满足需求。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i =0;
        while(i<n){
            int sumOfCost=0,sumOfGas=0;
            //保存前进的加油站个数
            int cnt=0;
            while(cnt<n){
               //在这个循环中，i不动，cnt移动，当cnt移动n次时表示已经绕路线一周
                int j=(i+cnt)%n;
                sumOfCost+=cost[j];
                sumOfGas+=gas[j];
                if(sumOfCost>sumOfGas){
                    break;
                }
                cnt++;
            }
            if(cnt==n){
                return i;
            }else{
                i=i+cnt+1;
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中N为数组长度，我们对数组进行了单次遍历。
• 空间复杂度：O(1)