[리트코드] 724. Find Pivot Index

724. Find Pivot Index

오른쪽 숫자들의 합과 왼쪽 숫자들의 합이 같아지는 피벗의 위치 찾기

[1, 8, 2, 9, 2, 3, 6]
: 9
[2, 5, 7]
: -1 (가능한 피벗이 없음)

Brute-force?

o(n) * n -> o (n ^ 2) 비효율적임

sliding

전체 합계를 구해준다.

피벗을 0부터 한 칸씩 움직이면서 right sum에는 빼고 left sum에는 이전 피벗 값을 더해준다.

right sum과 left sum이 같아지는 지점을 찾는다.

[1, 8, 2, 9, 2, 3, 6]
​
0 | sum() - 1
1 + 0 | sum() - 1 - 8
8 + 1 + 0 | sum() - 1 - 8 - 2
.
.
.

전체 합계를 구하는데 O(n)

매번 오퍼레이션이 O(1)이고 n번이므로 O(n)

총 O(n)

전체 코드

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        right_sum = sum(nums)
        left_sum = 0
        prev = 0
        
        for i in range(len(nums)):
            left_sum += prev
            right_sum -= nums[i]
            prev = nums[i]
            
            if left_sum == right_sum:
                return i
        
        return -1