附上原題：
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.
剛看題目的時候以為又是一道動態(tài)規(guī)劃題涝婉，看完題目后發(fā)現并不是哥力。題目已經給出承諾，如果有解墩弯，則一定存在唯一解吩跋。如果我們按照常規(guī)思路，把所有的解都遍歷一遍渔工，那么一次需要遍歷N個站锌钮，總共遍歷N次，時間復雜度為O(n^2)引矩。在這道題目中梁丘，我們介紹一種叫做“尺取法”的算法技巧侵浸。
尺取法通常是指對數組保存一對下標（起點、終點）氛谜，然后根據實際情況交替推進兩個端點直到得出答案的方法掏觉，這種操作很像是尺蠖（日本中稱為尺取蟲）爬行的方式顧得名。
回到我們的問題上值漫，題目中給出了每個加油站的可加油量以及從當前加油站到下一個加油站的代價澳腹。如果從某個加油站出發(fā)可以繞線路一圈，那么返回該加油站的索引惭嚣。我們先來將問題做一個轉化：將每個站的加油量減去從當前加油站到下一個加油站的代價遵湖，即等于當前加油站到下一個加油站凈剩余的油量，如果能保證從某個加油站出發(fā)到終點的過程中晚吞，所有凈剩余油量的累加都不小于0延旧，那么該問題有解。用文字描述可能比較抽象槽地，我們直接來看一個比較簡單例子：
example:
gas = [2, 4]
cost = [3, 2]
每個汽油站的凈剩余油量
remainders = [-1, 2]
若從第一個加油站開始累加迁沫，先得到-1，顯然不符合要求捌蚊。
如果從第二個加油站開始集畅，先得到2，再加上-1等于1缅糟，每一次的結果都不小于0挺智。因此符合要求。
利用尺取法窗宦，我們可以設計出如下算法：
1 begin = end = sum = 0初始化
2 如果end沒有到達終點并且sum不小于0赦颇，則sum加上下一個加油站的凈剩余量，將end加1
3 如果2中無法滿足sum不小于0赴涵，則將sum減去起點加油站的凈剩余量媒怯，并且將起點設為從當前起點的下一個加油站。如果2中end到達了終點髓窜，則返回begin扇苞。
4 如果begin超過了加油站的數量，說明不存在有效的解寄纵，返回-1鳖敷。否則繼續(xù)執(zhí)行第2歩。
附上代碼：
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
//先計算每個加油站的凈剩余油量
vector<int> remainders;
for (int i = 0; i < gas.size(); i++) {
remainders.push_back(gas[i] - cost[i]);
}
int stationNums = gas.size();
int sum = 0, begin = 0, end = 0;
while (begin < stationNums) {
while (end < (stationNums + begin) && sum >= 0) {
sum += remainders[end % stationNums]; //因為是環(huán)路程拭，這里記得用模運算
end++;
}
if (sum >= 0) {
return begin;
}
sum -= remainders[begin++];
}
return -1;
}
};
