• 第一种想法就是每个位置都遍历一遍 O(n*n) 
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int ans[] = new int[gas.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = gas[i] - cost[i];
        }
        for (int i = 0; i < ans.length; i++) {
            int j = 0;
            int temp = 0;
            while (j < ans.length) {
                temp += ans[(i+j)%ans.length];
                if (temp < 0) break;
                j++;
            }
            if(j==ans.length)return i;
        }
        return -1;
    }
}

  • 第二种想法 优化上面的代码 也就是找中断点 然后接着后面查找

    class Solution {
  public int canCompleteCircuit(int[] gas, int[] cost) {
      // 加油站起始点
      int start = 0;
      // 从0-start需要补充多少油 
      int total = 0;
      // 从start开始到i 油量   
      int tank = 0;

      for(int i=0; i<gas.length; i++) {
          // 走过ith 加油站还剩下多少油 （>0）
          // 要走ith 加油站差多少油 （<0）
          tank += gas[i] - cost[i];
          // 油不够了，start不能做起始点；
          // 且start ～ i 都不可做起始点。
          if(tank < 0) {
              start = i+1;
              total += tank;
              tank = 0;
          }
      }
      return total+tank >= 0 ?start : -1;
  }
}