前綴和

這篇文章，會帶著大家複習以前學過的前綴和框架， 並且以區間和的概念與應用為核心， 貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。 前綴和 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的同學

題目會給我們一張資料表Queue，代表乘客排隊上車的情境。 裡面分別有person_id、 person_name 、weight、turn等欄位，分別代表乘客ID、乘客姓名、乘客重量、乘客排隊的順序。 要求我們判斷，在不超重的條件下，最後一位上車的乘客是誰。

在學習過比較基本的DP模型 費式數列、爬樓梯、找零錢...等之後， 來看一個比較進階而且實用的DP模型，前綴和(Prefix sum)， 可以再加以延伸推廣，來計算 區間和(Range Sum)。