『 LeetCode 技巧』Prefix Sum 前綴和

前言

最近開始學習資料結構，搭配著 LeetCode 進行練習，發現有很多解題的觀念都可以通用！
這次就來説說這次解到的題目，有錯誤的地方還請多多指教 >_<
以下為題目連結：1171. Remove Zero Sum Consecutive Nodes from Linked List

Prefix Sum 前綴和

什麼是前綴和呢？簡單來說，就是將前面的數相加得到的一個新的和陣列。
而得到的新陣列可以讓我們做一些事，求區間和（subarray）就是基礎應用之一。

當題目是整數列而且出現需要”子數列”或”連續的子數列”時，就能利用這著概念去解題，效果可說是相當不錯。

1
2
3

let array = [1, 2, 4, 7, 3, 5];
// 取得前綴和，累加 array[0:i-1] 得到 prefixSumArray[i]
let prefixSumArray = [1, 3, 4, 14, 17, 22];

在實作上，我們就可以直接使用這個數列進行累加，就不用再去遍歷一次 array。

解題絲路

題目

先來看題目~
在給定的鏈結裡面，重複扣除總和為 0 的連續數列，直到沒有這類的數列為止。
最後返回剩餘的鏈結。

寫之前再到最下面看一下”條件(Constraints)”，這很重要呦！

算法

看到”連續數列”，我們就可以試著利用 Prefix Sum。
另外補充，一般來說，前綴和會和 Map 一起做使用。

建構一個 MAP 來儲存具有同累加值的最後節點的累積和。
因為最後一個節點的下一個數值是我們要建造和連結輸出的地方。
將 MAP 給實作出來

var removeZeroSumSublists = function (head) {
  // 如果 head == false，return head
  if (!head) {
    return head;
  }
  // 概念 prefix sum map
  let newNode = new ListNode(0);
  newNode.next = head;

  let current = newNode,
    prefixSumMap = new Map(),
    sum = 0;

  while (current) {
    sum += current.val;
    prefixSumMap.set(sum, current);
    current = current.next;
  }

  current = newNode;
  sum = 0;
  while (current) {
    sum += current.val;
    current.next = prefixSumMap.get(sum).next;
    current = current.next;
  }
  return newNode.next;
};

類似題型

560. Subarray Sum Equals K

643. Maximum Average Subarray I