活用天秤模型: 尋找平衡軸心點_Leetcode Find Pivot Index #724
題目敘述
題目會給我們一個整數陣列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
你可能也想看
