LeetCode 解題：Find Pivot Index

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/find-pivot-index/

中文描述

給定一個整數陣列 nums ，找出某目標索引位置 Pivot Index，讓目標索引位置的左邊元素陣列元素總和等於目標索引位置的右邊陣列元素總和，總和不包含目標索引位置之值。

範例一：

輸入 nums = [1, 2, 3, 4, 2, 2, 2] 

輸出  3

因為  [1, 2, 3] 總和等於 6 等於 [2, 2, 2]總和

範例二：

輸入 nums = [3, -3, 3] 

輸出  0

因為  [] 總和等於 0 等於 [-3, 3] 總和

解法一：

暴力法。對每一個索引位置算出左邊元素陣列元素總和 leftSum 與右邊元素陣列元素總和 rightSum 是否相等。

Python Code

class Solution:

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

        total = sum(nums) # 陣列總和

        leftSum = 0 # 左邊總和

        for i in range(len(nums)): # 從左邊索引0開始找起

            rightSum = sum(nums[i+1:]) # 右邊總和

            leftSum = total - rightSum - nums[i] # 左邊總和

            if leftSum == rightSum: # 若一樣

                return i # 找到 Pivot Index

        return -1

解法二：

算出右邊總和 rightSum，與 leftSum 等於零。從索引位置0開始依序從 rightSum 刪除 nums[i] 數值，判斷 leftSum 是否等於 rightSum，若有，則找到。leftSum 開始依序加入 nums[i] 數值。

Python Code

class Solution:

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

        rightSum = sum(nums) # 右邊總和

        leftSum = 0 # 左邊總和

        for i in range(len(nums)): # 從左邊索引0開始找起

            rightSum -= nums[i]

            if leftSum == rightSum: # 若一樣

                return i # 找到 Pivot Index

           

            leftSum += nums[i]

        return -1