prefixsum
含有「prefixsum」共 9 篇內容
全部內容
發佈日期由新至舊
Prefix Sum（前綴和）是一種用於計算陣列中任意區間和的高效方法。
前綴和算是一種犧牲空間換取時間效能提升的策略。
這在需要頻繁查詢區間和的情況下特別有用。
一開始，初始化時花費O(n)時間，掃描每個元素累加，建立一個prefix sum table，
接著，提供query介面查詢區間和
付費限定
題目敘述 Subarray Sums Divisible by K
給定一個整數陣列，請計算有幾個區間和能夠整除k的連續區間?
測試範例
Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
剛吃飽，來杯茶吧！🍵
這篇文章，會帶著大家複習以前學過的前綴和框架，
並且以區間和的概念與應用為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
前綴和 prefix sum框架 與 區間和計算的關係式
接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目
(請讀者、或觀眾
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧，時間複雜度為O(n)，空間複雜度為O(n)。
題目敘述
題目會給定一個鏈結串列的起始點，要求我們把其中區間總和為0的部分刪除掉。
例如
1→ 2 → -2 → 3 → 4
裡面有一段是2 → -2 區間總和為零，所以簡化刪除後變成
1→ 3 → 4
題目的原文敘述
測試範例
Example 1:
Input: head
付費限定
題目敘述
題目會給定一棵二元樹的根結點，
要求我們計算滿足局部路徑節點和=targetSum的數目有多少?
註:
局部路徑節點和
=由節點a往下走到某個節點b，這個區間內的節點值總和
題目的原文敘述
測試範例
Example 1:
Input: root = [10,5,-3,3
付費限定
題目敘述
假想一位自行車手正在公路旅行，旅行起始點從海拔為0的地方開始出發，給定每個紀錄點的高度位移向量陣列gain，請問整趟旅途中的海拔最高點是多少?
題目的原文敘述
測試範例
Example 1:
Input: gain = [-5,1,5,0,-7]
Output: 1
Expl
題目敘述
題目會給我們一個輸入陣列nums，和一個指定的k值。
請問，在輸入陣列nums中，有幾個子陣列的元素總合恰好為k ？
例如: nums = [1,2,3], k = 3
則有兩個子陣列的元素總合為3，分別是[1,2] 和 [3]
如果是第一次聽到或接觸前綴和prefix的同學
這題的題目在這裡:Find Pivot Index
題目敘述
題目會給我們一個整數陣列nums，要求我們計算平衡軸心點在哪?
平衡軸心的意思就是軸心點索引左側的元素總合 = 軸心點索引右側的元素總合
