560. Subarray Sum Equals K

解題程式碼

var subarraySum = function (nums, k) {
  const numsMap = new Map([[0, 1]]);
  let sum = 0;
  let counter = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    if (numsMap.has(sum - k)) {
      counter += numsMap.get(sum - k);
    }
    if (!numsMap.has(sum)) {
      numsMap.set(sum, 1);
    } else {
      numsMap.set(sum, numsMap.get(sum) + 1);
    }
  }
  return counter;
};

// example
// k = 3，nums = [-2,1,2,-2,5,-2,1]
// prefixSum   prefixSum count   counter (prefixSum - k)
// 0           1
// -2          1
// -1          1
// 1           1                 +1 (1 - 3 = -2)
// -1          2
// 4           1                 +1 (4 - 3 = 1)
// 2           1                 +2 (2 - 3 = -1)
// 3           1                 +1 (3 - 3 = 0)

解題思路、演算法

這題使用 hashMap + prefix sum 解題，在遍歷陣列的過程中，我們去將當前遍歷過的所有元素總和存在一個變數 sum，而每次遍歷的 sum 和其出現次數就存在 hashMap 裡面，當 sum - k = n，n 有存在於 hashMap 時就代表 sum - n = k，其中一定有連續陣列元素總和加起來為 k，因此可以將 n 在 hashMap 出現的次數(其 value) 加入到計數的 counter。

以下圖為例，當我們遍歷到索引 5，元素值 -2 時，prefixSum 為 2，2 - 3 = -1，(sum - k = n)，所以也就是說我們去找前面的 prefixSum 有沒有出現過 -1，從圖可以發現有出現，還出現了兩次，分別是在索引為 1 和 3 的時候，代表 2 - (-1) = 3，(sum - n = k)，因此可以找出兩個連續子陣列和為 k。

這裡有個 edge case 要處理的是，若 prefixSum = k 時，代表當前遍歷過的元素組成的陣列可以加入計數一次，這有可能在第一個元素就會發生，所以預先幫 hashMap 加上 [0, 1]，prefixSum - k = 0 時，查表就有對應的次數可以加入到計數的 counter。

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

贾考博 LeetCode 560. Subarray Sum Equals K - Prefix Sum 必会题目！

283. Move Zeroes

解題程式碼

var moveZeroes = function (nums) {
  let p = 0;

  for (let i = 0; i < nums.length; i++) {
    if (nums[i]) {
      const temp = nums[i];
      nums[i] = nums[p];
      nums[p] = temp;
      p++;
    }
  }
};

解題思路、演算法

這題我們將整個陣列遍歷，如果有碰到不是 0 的數字，就和 pointer 索引的陣列值做交換，然後 pointer+1

遍歷經過幾個元素就會變成 pointer 索引的那個值會是 0，這樣就可以和當前遍力到的非 0 元素做交換，逐漸將所有 0 換到陣列的後方

// [2, 0, 1, 0, 3, 12] p = 0, i = 0 swap 2 self, p = 1
// [2, 0, 1, 0, 3, 12] p = 1, i = 1 no swap
// [2, 1, 0, 0, 3, 12] p = 1, i = 2 swap 0 & 1, p = 2
// [2, 1, 0, 0, 3, 12] p = 2, i = 3 no swap
// [2, 1, 3, 0, 0, 12] p = 2, i = 4 swap 0, 3, p = 3
// [2, 1, 3, 0, 0, 12] p = 3, i = 5 swap 0, 12, p = 4

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(1)

參考資料

Move Zeroes - Leetcode 283 - Python

253. Meeting Rooms II

題目說明

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Comstraints

1 <= intervals.length <= 10^4
0 <= starti < endi <= 10^6

解題程式碼

const minMeetingRooms = (intervals) => {
  const start = intervals.map(e => e[0]).sort((a, b) => a - b);
  const end = intervals.map(e => e[1]).sort((a, b) => a - b);

  let rooms = 0;
  let tempRooms = 0;
  let startP = 0;
  let endP = 0;

  while (startP < intervals.length) {
    if (start[startP] < end[endP]) {
      startP++;
      tempRooms++;
    } else {
      endP++;
      tempRooms--;
    }
    rooms = Math.max(rooms, tempRooms);
  }
  return rooms;
}

解題思路、演算法

假設有一個 input 為 [[0,30],[5,10],[10,15]]，我們其實可以把 input 拆分成兩個陣列並先做排序，一個集中放各會議開始的時間 [0, 5, 10]，另一個放各會議結束的時間 [10, 15, 30]，然後利用兩個指針去移動到指定的陣列元素。例如:

時間為 0 的時候，會議室會使用一間，時間為 5 的時候，會議室會再使用一間，總共為 2。

而時間為 10 的時候，有一場會議結束，另一場會議開始，會議室會使用一間，總共還是為 2。

接下來都沒有新的會議了，所以時間為 15、30 時，進行的兩場會議依序結束。得出最多需要兩個會議室。

解法的時間、空間複雜度

時間複雜度: O(n * log n)
空間複雜度: O(n)

參考資料

Meeting Rooms II - Leetcode 253 - Python

leetcode 中文 | Meeting Rooms II | Merge Intervals 基礎概念 5 - Python - LeetCode 253

用 MinHeap (Priority Queue) 解的做法