Daily LeetCode 724. Find Pivot Index

https://leetcode.com/problems/find-pivot-index/

Easy

问题描述：

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where ==the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index==.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Example 2:

Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Note:

• The length of nums will be in the range [0, 10000].
• Each element nums[i] will be an integer in the range [-1000, 1000].

题目分析：

给定一个数组，我们需要找到一个分割点，使得分割点两边的和相等，如果存在多个点，则返回最左边的，如果不存在，则返回-1。

我们只需要一次遍历，就能够解决这个问题。初始状态下的index为0，此时leftSum=0, rightSum=sum(nums)，在遍历过程中，不断更新leftSum, rightSum，就可以找到最左边的分割点。

以题目中所给例子为例，遍历过程中和的更新情况如下：

index:  0 , leftSum:  0 , rightSum:  27
index:  1 , leftSum:  1 , rightSum:  20
index:  2 , leftSum:  8 , rightSum:  17
index:  3 , leftSum:  11 , rightSum:  11	-->return index

代码：

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        leftSum, rightSum = 0, sum(nums)
        
        for index, num in enumerate(nums):
            rightSum -= num
            if leftSum == rightSum:
                return index
            leftSum += num

        return -1