134. Gas Station

problem description

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 in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique. Both input arrays are non-empty and have the same length. Each element in the input arrays is a non-negative integer.

Example 1:

Input:  
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input:  
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

algorithm thought

用gas[i]减去cost[i]是能得到每次经过一个位置消耗的汽油量的。

对于这题来说最简单的方法就是，用双重循环遍历数组，得到从每一个地点开始的消耗量，要是能顺时针走完就返回index，这样也能ac，但是时间复杂度O(n²)。

这题其实可以用O(n)时间解决，开始随机选一个位置，然后判断当前汽油量是正还是负，如果是负就将开始位置向挪动一位，看能否增加汽油量，否则就可以向后移动一位。知道两位置重合，这时候判断总的汽油量是否为正，如果是正就代表能走完。这也是用类似twosum的两指针逼近法，目标值就是最后汽油量需要大于0。

code

//原始二维数组方法
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        bool bo=true;
        for(int i=0;i<gas.size();++i)
            gas[i]-=cost[i];
        for(int i=0;i<gas.size();++i){
            if(gas[i]>=0){
                int t=0;
                bo=true;
                for(int j=0;j<gas.size();++j){
                    int pos=(i+j)%gas.size();
                    t+=gas[pos];
                    if(t<0){
                        bo=false;
                        break;
                    }
                }
                if(bo)
                    return i;
            }
        }
        return -1;
    }
};

//逼近办法
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

       int start = gas.size()-1;
       int end = 0;
       int sum = gas[start] - cost[start];
       while (start > end) {
          if (sum >= 0) {
             sum += gas[end] - cost[end];
             ++end;
          }
          else {
             --start;
             sum += gas[start] - cost[start];
          }
       }
       return sum >= 0 ? start : -1;
    }
};

//顺序遍历方法
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int start=0,total=0,tank=0;
        for(int i=0;i<gas.size();++i){
            if((tank=tank+gas[i]-cost[i])<0){
                total+=tank;
                tank=0;
                start=i+1;
            }
        }
        return tank+total<0?-1:start;
    }
};

algorithm analysis

第一个方法时间复杂度O(n²)，毋庸置疑是最慢的，第二种和第三种方法时间复杂度都是O(n).