活用天秤模型: 尋找平衡軸心點_Leetcode Find Pivot Index #724

Elena Mozhvilo on Unsplash

這題的題目在這裡:Find Pivot Index

題目敘述

題目會給我們一個整數陣列nums，要求我們計算平衡軸心點在哪?

平衡軸心的意思就是軸心點索引左側的元素總合 = 軸心點索引右側的元素總合

例如

整數陣列nums=[1,2,2,7,2,3]

7左側的元素總合為 1 + 2 + 2 = 5

7右側的元素總合為 2 + 3 = 5

所以7是平衡位置，其索引位置為3

所以平衡軸心索引位置 = 3

答案為3

測試範例

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

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

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0 

約束條件

Constraints:

• 1 <= nums.length <= 10^4
• -1000 <= nums[i] <= 1000

演算法

這題除了古典的prefix sum前綴和的演算法之外，還有一個精彩巧妙的問題簡化技巧可以使用，就是天秤秤重的模型。

把每個整數想成重量不一的砝碼，數字小的就是小砝碼，數字大的就是大砝碼。

原本軸心點索引左側的元素總合 = 軸心點索引右側的元素總合 就轉化成

中小學學過的經典秤重問題，請問軸心點移到哪，左右兩側總重量等重，天平達到平衡。

一開始讓左邊的盤子為空，總重量=0

讓右邊的盤子放上全部的砝碼，總重量 = 陣列元素總合。

接著，開始迭代，從右邊的盤子拿一個砝碼下來，假如達到平衡，則當下的索引i就是平衡的軸心點索引。
假如還沒達到平衡，則把這個砝碼放到左邊的盤子。接著反覆進行下一回合的迭代。

如果到最後，都沒辦法達成平衡，代表無解，返回-1

解說動畫

程式碼

class Solution:
　def pivotIndex(self, nums: List[int]) -> int:
　　
　　# Initialization:
　　# Left hand side be empty, and
　　# Right hand side holds all weights.
　　total_weight_on_left, total_weight_on_right = 0, sum(nums)

　　for idx, current_weight in enumerate(nums):

　　　total_weight_on_right -= current_weight

　　　if total_weight_on_left == total_weight_on_right:
　　　　# balance is met on both sides
　　　　# i.e., sum( nums[ :idx] ) == sum( nums[idx+1: ] )
　　　　return idx

　　　total_weight_on_left += current_weight

　　return -1

複雜度分析

時間複雜度: O(n)

線性掃描，掃過每顆砝碼，總共耗時O(n)

空間複雜度: O(1)

所用到的都是固定尺寸的臨時變數，為常數級別O(1)

關鍵知識點

這題除了古典的prefix sum前綴和的演算法之外，有興趣的讀者可以試著寫寫看。

(提示: prefix sum前綴和 可以在O(1)時間內求出range sum區間和)

還有一個精彩巧妙的問題簡化技巧可以使用，就是天秤秤重的模型。

把每個整數想成重量不一的砝碼，數字小的就是小砝碼，數字大的就是大砝碼。

原本軸心點索引左側的元素總合 = 軸心點索引右側的元素總合 就轉化成

中小學學過的經典秤重問題，請問軸心點移到哪，左右兩側總重量等重，天平達到平衡。

Reference:

[1] Python/Go/Java/JS/C++ O(n) sol. by Balance scale. [w/ explanation] - Find Pivot Index - LeetCode