Gas Station

1、基本思路

　　依次从每个加油站开始加，判断是否满足条件。O（n^2）的复杂度，会超时。

2、O（n）的方法

　　一种思路是，如果从 i 到 j 的油的余量和小于0，则开始点必定在 i 左边，所以如果小于0，开始点左移，大于0，到达的位置右移；

 1     int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
 2         // Note: The Solution object is instantiated only once and is reused by each test case.
 3         int begin = 0, end = 0;
 4         int sum = 0;
 5         int n = gas.size();
 6         int i = 0;
 7         while(n > 0){
 8             sum += (gas[i]-cost[i]);
 9             if(sum >= 0){
10                 end++;
11                 i = end;
12             }
13             else{
14                 begin--;
15                 if(begin<0)
16                     begin = gas.size()-1;
17                 i = begin;
18             }
19             n--;
20         }
21         if(sum < 0)
22             return -1;
23         return begin;
24     }

　　另外一种思路时，用两个变量sum和total，它们都逐次加上油的余量，如果sum小于0，那么开始点更新为当前坐标，sum归零。遍历结束后，如果total小于0则没有方案，否则返回开始坐标。

 1     int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
 2         // Note: The Solution object is instantiated only once and is reused by each test case.
 3         int n = gas.size();
 4         int res = 0, sum = 0, total = 0;
 5         for(int i = 0; i < n; i++){
 6             sum += (gas[i]-cost[i]);
 7             total += (gas[i]-cost[i]);
 8             if(sum < 0){
 9                 res = (i+1)%n;
10                 sum = 0;
11             }
12         }
13         if(total < 0)
14             return -1;
15         return res;
16     }