切換
舊版
前往
大廳
主題

LeetCode - 303. Range Sum Query - Immutable 解題心得

Not In My Back Yard | 2020-10-01 00:00:48 | 巴幣 2 | 人氣 163

題目連結:


題目意譯:
給定一整數陣列,求得第 i 個數字到第 j 個數字之間(含 i 與 j ,且 i ≦ j)的數字和。

限制:
你可以假設陣列不會有任何的更動。
會有多次的函式 sumRange 之呼叫(就是同一個陣列求多次區間和)。
0 ≦ nums.length ≦ 10 ^ 4
-10 ^ 5 ≦ nums[i] ≦ 10 ^ 5
0 ≦ i ≦ j < nums.length



範例測資:
範例:
給定 nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3


解題思維:
參見先前關於前綴和(Prefix Sums)的此題




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

創作回應

更多創作