问题

到站加油，去站减油。

是否有站，能为起点，绕行一圈，油量非负？

算法：双指针+贪心 时$O(N)$ 空$O(N)$

算法基础课模板题：最长连续不重复子序列

双指针本质是对暴力算法的模拟。这道题的暴力解法很直观：枚举所有起点，看是否能环绕一圈。

可以看到暴力解法重复计算了很多次，怎么减少重复计算？由于这本质是一个线性区间问题，我们可以用两个递增的双指针避免大量重复计算：
1. 首先预处理gas和cost数组成一个sum数组，得到到达某点真正的耗油量。并且将sum数组扩展成2n，以便处理环绕
2. 用两个指针j, i分别模拟起点和终点，用一个变量tot记录当前余油量。
3. i不断向后移动，同时tot减去i处的耗油量，如果tot<0, 则起点j向后移动，同时tot加上j处的耗油量

注意，上面陈述的是耗油量，实际代码实现用的是加油量。

下面关键是证明双指针算法的正确性。这类题的证明思路就是看我们的算法能不能正确地获取到答案。。可以假设正确的起点在某一点上，如果我们算法的起点到达了这一点，那么就不会错过，会得出正确的结论。

那么会不会还没到就提前得出一个错误的起点呢？不会，因为错误的起点必定导致无法环绕一圈，使得我们的起点继续向后移动。

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        vector<int> sum(2*n);
        for(int i = 0; i < 2*n; i ++){
            sum[i] = gas[i%n] - cost[i%n];
        }

        int tot = 0;
        for(int i = 0, j = 0; i < 2*n && j < n; i ++){
            tot += sum[i];
            while(tot < 0 && j <= i){ // j <= i 意味着 j可以等于i, 相当于判断能不能将i这个位置当作起点
                tot -= sum[j ++]; 
            }

            if(i - j + 1 == n){
                return j;
            }

        }

        return -1;
    }
};