134. Gas Station

리트코드 134. Gas Station

 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total=0
        curr=0
        res = 0
        for i in range(len(gas)):
            total += gas[i] - cost[i]
            curr += gas[i]- cost[i]
            if curr<0:
                curr = 0
                res = i+1
        return res if total >=0 else -1

        # total, curr, 인덱스 값을 놓고
        # 순회하면서 가스-비용 계산한다
        # 만약 현재 노드까지에서 가스 - 비용이 마이너스라면 이 시작 지점으로 갈 수 없다는 뜻이므로
        # curr를 0으로 만들고 res에 하나를 더한다
        # 시작 지점을 하나씩 늘려 루프를 끝내고 total 이 0 이상이라면 완주할 수 있음

        # 시간복잡도는 gas 길이만큼 for 한번이므로 O(n)
        # 공간복잡도는 O(1)

처음에는 누적합으로 시작 포인트를 기점으로 모두 더한 배열을 한 칸씩 비교하다가 TLE가 났다