题目链接：Gas Station

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]油量。可以从任意一个加油站出发，如果可以绕环一周，返回出发地的index，否则返回-1。

描述起来比较麻烦的题目。从i出发，计算最远能否走回i。如果可以，返回i；否则，下次就从能到达的最远处j重新出发（如果j小于i的号，说明无法绕环一圈，返回-1）。起初的i从0开始。这样，每个位置访问1便，时间复杂度O(n)。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution
{
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        int n = gas.size(), i = 0;
        while(i < n)
        {
            int s = gas[i] - cost[i], j;
            for(j = (i + 1) % n; j != i && s >= 0; j = (j + 1) % n)
                s += gas[j] - cost[j];
            
            if(s >= 0)
                return i;
            
            if(j > i)
                i = j;
            else
                return -1;
        }
    }
};