主題

LeetCode - 724. Find Pivot Index 解題心得

Not In My Back Yard | 2021-01-02 00:00:05 | 巴幣 0 | 人氣 18

題目連結:


題目意譯:
給定一個整數陣列 nums ,撰寫一函式回傳陣列的「樞紐」之索引值(從 0 開始數)。

我們定義樞紐為滿足陣列上的某位置之數字,其左邊的所有數字之和等於其右邊所有數字之和。

如果樞紐不存在,我們應回傳 -1 。如果有多個樞紐,則回傳最左邊的樞紐之索引值。

限制:
nums 的長度位於 [0, 10000] 範圍之中。
nums[i] 之值位於 [-1000, 1000] 範圍之中。



範例測資:
範例 1:
輸入: nums = [1,7,3,6,5,6]
輸出: 3
解釋: 索引值 3 的位置(nums[3] = 6)之左邊數字之和等於其右邊數字之和。

範例 2:
輸入: nums = [1,2,3]
輸出: -1
解釋: 不存在任何索引值滿足題目要求。


解題思維:
先建立 nums 的前綴和(Prefix Sums)陣列,參見這題

假設前綴和陣列 P ,且 P[0] = 0 、 P[i] = nums 第 0 個元素到第 i - 1 個元素之和(i > 0),則對於任意位置 nums[i] 其左邊的數字和恰好為 P[i] 、 右邊的數字和恰好為 P[nums.size()] - P[i + 1],因此我們就可以快速地判斷左右兩邊的數字和有無相等。如果有就直接回傳該位置 i 即可(i 從 0 開始跑,便可以找到最左邊的樞紐,如果有的話)。

如果沒有任何符合的,此時再回傳 -1。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作