134. Gas Station
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
sum, start, fuel = 0, 0, 0
for i in range(n):
sum += gas[i] - cost[i]
if fuel + gas[i] - cost[i] < 0:
start = i + 1
fuel = 0
else:
fuel += gas[i] - cost[i]
if sum < 0:
return -1
return start
這個題目如果我們利用窮舉，一定可以找到開始的加油站，但是這樣一定不是最好的方法，因此要花時間去分析題目。
首先，我們可以知道的是題目有說：雖然可能沒有解，但是如果有解一定存在著唯一解，自此我們可以拆開分析：
我們可以先分析沒有解的情況，沒有解的情況我們可以去想像，如果我在某個站沒有油了，無法前往下一站，那就一定是無解嗎？我們不可以這樣斷言，因為可能只是我們的出發站比較不好而已，因為題目要我們找的就是可行的出發站，所以只是無法前往下一站，我們無法斷言就是無解。
因此我們就去想，如果我們每個站都試過了，但是還是無法完成所有的旅途，那代表的就是，不管我怎麼出發，加油站可以提供的油，一定小於我所消耗的，那在這種情況下，我是一定不可能找出任何一個解的。
也就是說反過來看，如果加油站的油量大於或是等於成本，那就一定可以完成旅程，這一點的說明是，因為只要總和大於成本，如果我在某一個地方接連消耗掉大量成本，那就一定會在這個路線的另外一段接連的加上油，才能讓總成本大於或是等於零。
用一個極端一點的例子來說，如果我有一段旅程每次的消耗大於加油，那就會產生大量赤字，因此在我從赤字開始轉正的那個點開始，就可以確定後面的旅程一定要有大量的加油，我才能補足之前的赤字。
不過如果我的一段旅程中，這樣的極端例子一直出現呢？這樣也是沒問題的，就只是我們要找到的出發站就又會再被往後推。但是！題目告訴了我們，題目存在著唯一解，因此當我們找到那個站的時候，我們就可以知道出發的加油站在哪裡。
因此綜合上面的分析，我們就可以線性的去找出加油站在哪裡，雖然說我們可以知道答案是唯一解，但是我們還是要把所有的加油站造訪完，要確定的是前面我們講過無解的狀態。
時間複雜度：