1. 题意：
   环形路线上有N个加油站，每个加油站有汽油gas[i],从每个加油站到下一站消耗汽油cost[i]
   问从哪个加油站出发能够回到起始点，如果都不能则返回-1；注意,解释唯一的；
   
   思路：
   累加在每个位置的left += gas[i]-cost[i].就是在每个位置剩余的油量，如果left一直大于0，
   则可一直走下去，如果left小于0,那么就从下一个位置重新开始计数，并且将之前欠下的多少记录下来，
   如果最终遍历完数组剩下的燃料足以弥补之前不够的，那么就可以到达，并返回最后一次开始的位置，否则返回-1；
   
   
   论证这种方法的正确性：
   1，如果从头开始，每次累计剩下的油量都为整数，那么没有问题，它可以从头开到结束
   2. 如果到中间的某个位置，剩余的油量为负了，那么说明之前积累下来的油量不够从这一战
   到下一站，那么就从下一站从新开始计数，为什么从下一站，而不是从之前的谋战呢？
   因为第一站剩余的油量肯定大于等于0的，然而到当前油量变负了，说明从第一站之后开始的话当前油量只会更少
   不会怎加，也就说从第一站之后，当前站之前的某站出发到当前站之前的某站出发到当前站出发的剩余
   的油量是不大可能大于0的，所以只能从下一站重新出发开始计算从下一站开始剩余的油量
   并且把之前欠下的油量也累加起来，看到最后剩余的油量是不是大于欠下的油量。
   
2. class Solution
3. {
4. public:
5.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
6.     {
7.         int start = 0;
8.         int lack = 0;
9.         int left = 0;
11.         for (int i=0; i<gas.size(); i++)
12.         {
13.             left += gas[i]-cost[i];
14.             if (left<0)
15.             {
16.                 start = i + 1;
17.                 lack += left;
18.                 left = 0;
19.             }
20.         }
22.         return left + lack >= 0 ? start : -1;
23.     }
24. };
25. 
    

需要着重理解为啥下一点可以从i+1开始

1. 若从i开始累加sum，当到j点时<0，说明从i开始到不了j+1点 由于可到达i+1,则diff[i]>=0，所以diff[i+1]...+diff[j]<0-diff[i]<=0,所以i+1不能到j点，
2. 由于i可以到i+2,则diff[i]+diff[i+1]>=0,所以diff[i+2]...+diff[j]<0-(diff[i]+diff[i+1])<=0,所以i+2不能到j点，
3. 以此类推可知[i,j]之间所有的点都不能到达j+1点

     classSolution {
     public:
         intcanCompleteCircuit(vector &gas, vector &cost) {
             vector diff;
             for(inti=0;i<(int)gas.size();i++)
                 diff.push_back(gas[i]-cost[i]);
             intsum=0;
             intstart=0;//标记开始的位置
             intend=0;
             for(inti=0;i<2*diff.size();i++) //由于是环路，最后一个可以走至此位置
             {
                 if(sum<0) //表示到达下一点(i+1)的剩余油量，如果大于等于0表示能够当前状态能够支撑到下一点
                 {
                     sum=diff[i%diff.size()];
                     start=i;
                     end=i;
                 }
                 else
                 { 
                     sum+=diff[i%diff.size()];
                     end=i;
                     if(end-start>=diff.size())
                         returnstart;
                 }
             }
             return-1;
         }
     };
   

// 解有且只有一个，所以只有从起点start处出发
// 才可以走完全程。这也指出了一个事实：那就是
// 从另外的起点出发，走到start-1时无法走下一步
// 到start，所以当出现本次剩余汽油量<0时，下一步
// 就有可能是真正的起点，至于是不是，要看总得汽油
// 量是不是大于0
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || cost == null || gas.length <= 0 || cost.length <= 0)
			return -1;

		int index = -1, remain = 0, total = 0;
		for(int i = 0; i < gas.length; i++){
			total += gas[i] - cost[i];
			remain += gas[i] - cost[i];
			// 如果本次剩余<0,说明不能由i走到i+1
			if(remain < 0){
				remain = 0;
				index = i;
			}
		}
		return total >= 0 ? index + 1 : -1;
    }
}

思路：
（1）枚举法：枚举从第一个位置开始，直到最后一个位置。

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

评论中的其它思路：

思路1（牛客923）：设置一个start,一个end

1. start每次向前走start++
2. 当每次总的汽油剩余量<0时，end--
   最后如果有解的话是在end位置

思路2（食肉大灰兔）:

1. 先计算，每个站res = gas-cost的值，求和，如果小于0则说明不可达
2. 从头开始当发现res >0 ,则开始计算res的和sum，如果sum<0时，则继续往后找res>0的位置，在继续计算sum值（此思路的依据就是一定有唯一值，且只会从res>0的位置开始）

C++ solution

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

        int leftOver = 0;
        int sum = 0;
        int start = 0;

        for (int j = 0; j < gas.size(); ++j) {
            leftOver += sub[j];
            sum += sub[j];
            if (sum < 0) {
                start = j + 1;
                sum = 0;
            }

        }
        if (leftOver < 0) {
            return -1;
        }
        return start;


    }
};

class Solution {
public:
    // 贪心算法 
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) 
    {
        int start = -1;
        int total = 0,sum = 0;
        for(int i=0;i<gas.size();i++)
        {
            sum += gas[i] - cost[i];
            total += gas[i] - cost[i];
            
            if(sum < 0)    // 不能达到该点i，则start到i-1之间的点都不能作为有效起点,将i作为新的起始点
            {
                sum = 0;
                start = i;
            }
        }
        return total >= 0 ? start+1 : -1;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        int left = 0;//邮箱中剩余的油量
        for(int i = 0; i < gas.size(); ++i)//起点
        {
            for(int j = 0; j < gas.size(); j++)//向前走加油站的个数
            {
                //每经过一个加油站后，邮箱中的油=之前剩余的油量+加油站的油量-本次消耗的油量
                left = left + gas[(i+j)%gas.size()] - cost[(i+j)%gas.size()];
                if(left < 0)//如果剩余油量为负数，换下一期起点重新开始
                {
                    left = 0;
                    break;
                }
                if(j == gas.size() - 1)//如果当前起点能走完所有加油站
                    return i;//返回当前起点
            }
        }
        return -1;//所有起点都不满足，返回-1
    }
};

• idea：

  1. 首先用gas_now来保存当前油量。
  2. 从0开始遍历，假如gas_now<0，则说明当前起点不可能完成旅程，且当前走过的路消耗的油量比加油量多。当gas_now<0时重新计算油量，并将起点设置为i+1。
  3. 证明为什么这个ans就是最终的答案。首先这个note有说明The solution is guaranteed to be unique。由2可知ans前的任意一个点都不可能为起点，因为那段路消耗油量比加油量多，且一点gas_now<0时即切换了起点。
  4. 前一个起点和当前起点之间的任意一个点也可能为答案。理由为，在前一个起点和当前起点过程中，保存下来的油量都大于0，加上这些油量从中间这些点出发都没法完成旅程，那么从这些点出发油量更少更不可能完成旅程。
  5. 再证明ans到n这些点不可能为起点。设 ，已知ans到j一路油量都是正的（假如出现负ans就改了，所以一定是正的）。那么从ans出发到n这段路保存下来的油量 比 从j出发到n这段路保存下来的油量多。又0~ans这段路的油量一定是负的（因为出现负才会换ans），假如从j出发都能完成旅程，那么从ans出发也一定能完成旅程，又只有一个答案，因此j不能成为起点。
  6. 以上前提都在total>=0的情况下，否则没有一个起点能完成旅途
     

• code

  class Solution {
  public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int ans = 0;
        int total = 0;
  
        int gas_now = 0;
        int n = gas.size();
  
        for (int i = 0; i < n; i++){
            gas_now += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if (gas_now < 0){
                gas_now = 0;
                ans = i+1;
            }
        }
  
        return total>=0?ans:-1;
    }
  };
  

```

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas.length<1 || cost.length<1 || gas.length!=cost.length)
            return -1;
        int left=0;
        int index=0;
        for(int i=0;i<gas.length;i++){
            left+=gas[i]-cost[i];
            if(left<0)
            {
                left=0;
                i=index++;
                continue;
            }
            if(i==gas.length-1)
                i=-1;
            if(i==index-1)
                return index;
            if(index>=gas.length)
                break;
        }
        return -1;
    }
}

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int start(0);int store(0);int tank(0);
        for(int i(0);i != gas.size();i++)
        {
            
        	if((tank += gas[i] - cost[i]) < 0)
        	{
            	store += tank;
                start = i + 1;
                tank = 0;
            }
        	
            
        }
        return (tank + store >= 0 ? start:-1);
    }
};

class Solution {
public:
    /**
     * 
     * @param gas int整型vector 
     * @param cost int整型vector 
     * @return int整型
     */
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // write code here
        int total = 0, last_fail = -1;
        for(int i=0, cur=0; i<gas.size(); ++i){
            cur += gas[i]-cost[i];
            total += gas[i]-cost[i];
            if(cur < 0) cur = 0, last_fail = i;
        }
        return total>=0 ? last_fail+1 : -1;
    }
};

	public int canCompleteCircuit(int[] gas, int[] cost) {



	        for (int i = 0; i < gas.length; i++) {



	            //计算节点后面的累计汽油



	            int number = 0;



	            for (int j = i; j < gas.length; j++) {



	                number = number + gas[j] - cost[j];



	                if (number < 0) {



	                    break;



	                }



	            }



	            if (i==0 && number>=0) {



	                return 0;



	            }



	            //计算节点前面的累计汽油



	            if (i>0 && number>=0) {



	                for(int j=0;j<i;j++) {



	                    number=number+gas[j]-cost[j];



	                    if(number<0) {



	                        return -1;



	                    }



	                }



	                if(number>=0) {



	                    return i;



	                }



	            }



	        }



	        return -1;



	    }

//忍不住想来一发用链表模拟...
//正好好像没看到用链表模拟的....
//写个链表给大家取笑一下.........
class Solution {
public:
struct ListNode{
    
    ListNode *next;
    int gas;
    int cost;
};
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        if(gas.size()==0) return -1;
        if(cost.size()==0) return -1;
        if(cost.size()!=gas.size()) return -1;
        int gasSum=0,costSum=0;
        for(int i=0;i<gas.size();i++)
        {
            gasSum+=gas[i];
            costSum+=cost[i];
        }
        if(gasSum<costSum) return -1;
        
        int N=gas.size();
        ListNode * pHead=new ListNode();
        ListNode *plast=pHead;
        pHead->gas=gas[0];
        pHead->cost=cost[0];
        for(int i=1;i<N;i++)
        {
            ListNode *pStation=new ListNode();
            plast->next=pStation;
            pStation->gas=gas[i];
            pStation->cost=cost[i];
            plast=pStation;
        }
        plast->next=pHead;
        ListNode *pNode=pHead;

        for(int i=0;i<N;i++)
        { 
           ListNode* pTemp=pNode;
           int leftGas=0;
           while(true)
           {
            leftGas+=pTemp->gas; //在开始的站先加油
            leftGas-=pTemp->cost;//然后看下到下一个站是否够油
            if(leftGas<0) break; //不够油,换个加油站
            else //够油到下一个站
            {
                if(pTemp->next==pHead) return i; 
                else pTemp=pTemp->next;
            }
           }
           pNode=pNode->next;
        }
            return -1;
    }
};

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        a = []
        for i in range(len(gas)):
            a.append(gas[i] - cost[i])
        if sum(a) < 0:
            return -1
        res = -1
        s = 0
        for i in range(len(a)):
            if res == -1:
                if a[i] >= 0:
                    res = i
                    s = a[i]
            else:
                if s + a[i] >= 0:
                    s += a[i]
                else:
                    res = -1
        return res

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int start = gas.size() - 1;
        int end = 0;
        int V = gas[start] - cost[start];
        while(start > end)
        {
        	if(V>=0)
        	{
        		V += gas[end] - cost[end];
        		end++;
			}else{
				start--;
				V += gas[start] - cost[start];
			}
		}
		return V>=0?start:-1;
    }
};