## 題解


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        i = 0

        while i < n:
            # 每次都需要重設一次
            sum_gas = 0
            sum_cost = 0
            cnt = 0 # 紀錄嘗試走過的加油站數
               
            # 嘗試從頭到尾遍歷所有加油站
            while cnt < n:
                j = (i + cnt) % n # 想像加油站是環形路徑
                sum_gas += gas[j]
                sum_cost += cost[j]
                if sum_gas < sum_cost: # 如果總花費要大於總油量，代表不可能走完所有加油站，隨即跳出
                    break
                cnt += 1 # 如果總花費小於總油量，代表還能繼續走，記錄一下走過幾個油站
            
            if cnt == n: # 代表上面的迴圈從頭到尾遍歷完了
                return i
            else: # 最巧妙的點，藉由透過上面的迴圈，來跳過已經知道沒辦法走到的加油站路徑
                i = i + cnt + 1 # 為何要加一？因為上面迴圈遍歷的範圍是 x -> y 之間的所有加油站 （包含 x 和 y），既然已知 x -> y 不可能走完，那自然從 y 的下一個加油站開始便利就好了
        return -1