724. Find Pivot Index.md

724. Find Pivot Index

Algoritum 1

• use one pointer to move and adjust left sum and right sum in each iter.

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:

        for i in range(len(nums)):
            if i == 0:
                l_sum = 0
                r_sum = sum(nums[1:])
            else:
                l_sum += nums[i-1]
                r_sum -= nums[i]
            
            if l_sum == r_sum:
                return i;
        return -1

Algorithm 2: Prefix Sum

• use total sum and left sum to find right sum.

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:

        total_sum = sum(nums)
        left_sum = 0
        for i, num in enumerate(nums):
            right_sum = total_sum - num - left_sum
            if right_sum == left_sum:
                return i
            left_sum += num
        return -1