128. Longest Consecutive Sequence

解題程式碼

var longestConsecutive = function (nums) {
  const numsSet = new Set(nums);
  let counter = 0;

  for (let i = 0; i < nums.length; i++) {
    let curNum = nums[i];
    if (!numsSet.has(curNum - 1)) {
      let tempCounter = 0;
      while (numsSet.has(curNum)) {
        tempCounter++;
        curNum++;
      }
      if (tempCounter > counter) counter = tempCounter;
    }
  }

  return counter;
};

解題思路、演算法

首先我們遍歷陣列一次，用一個 hashTable 去記錄陣列內所有出現過的元素值。

然後再遍歷陣列一次，檢查每個元素 n，n - 1 時是否存在於 hashTable，如果不存在我們可以把它當作是一組連續數字的開頭，然後依序去驗證 n + 1、n + 2...是否存在於 hashTable，然後直到數字不再連續後，得出這次連續數字的次數，如果比儲存最大連續數字次數 counter 變數的值更大，就去取代該值，便能得出最終結果。

雖然 for 迴圈裡還有一個 while 迴圈，但以範例 input [100,4,200,1,3,2] 來說，只有 1、100、200 時會進入迴圈，也就是整個 for 循環中，同個元素最多只會被拿來確認一次，不會隨著陣列長度增加而增加比對次數，所以時間複雜度為 O(n)。

解法的時間、空間複雜度

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

參考資料

189. Rotate Array

解題程式碼

var rotate = function (nums, k) {
  const length = nums.length;
  k %= length;

  const reverse = (i, j) => {
    while (i < j) {
      const temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;

      i++;
      j--;
    }
  };
  reverse(0, nums.length - 1);
  reverse(0, k - 1);
  reverse(k, nums.length - 1);
};

解題思路、演算法

這題的 Follow up 提到可以用空間複雜度 O(1) 去解題，所以可以得知有機會透過交換值 swap 的方式做出來。

看別人的解法發現，原來可以將 input 陣列反轉一次，然後從 k 的索引位置去切分陣列，兩個子陣列再反轉一次後合併，就是結果。

ex: input 為 [1,2,3,4,5,6,7]，第一次反轉後變成 [7, 6, 5, 4, 3, 2, 1] ，根據 k = 3 拆分為 [7, 6, 5] 和 [4, 3, 2, 1]，兩個陣列各自反轉後得 [5, 6, 7, 1, 2, 3, 4]。

解法的時間、空間複雜度

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

參考資料

525. Contiguous Array

解題程式碼

var findMaxLength = function (nums) {
  const numsMap = new Map();
  let length = 0;
  let sum = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i] ? 1 : -1;

    if (!numsMap.has(sum)) {
      numsMap.set(sum, i);
    } else {
      length = Math.max(length, i - numsMap.get(sum));
    }
    if (sum === 0) length = i + 1;
  }

  return length;
};

解題思路、演算法

這題的解法很推薦看 花花酱 LeetCode 525. Contiguous Array 的圖解，關鍵的思考方式就是假設 input [1,1,1,0,1,0,0]，

我們用 i 代表遍歷的索引值，可以發現在 i = 0 時，1 和 0 出現的次數相同，i = 6 時，1 和 0 出現的次數相同，所以可以得知在此之間(索引 1~6)的子陣列 1 和 0 出現次數都相同，因此在遍歷過程中，將最長的長度存入一個變數，最終就能求得最大的長度。

在程式碼實作方面，將 input 陣列的 0 看成 -1，去和 1 做加減，i 索引前 i+1 個數字加起來的值，若沒出現在 hashMap 過，就當作 hashMap 的 key，而索引 i 就當作 value。當然，如果前面數字加起來總合為 0，那前面數字的總長度就可能是最大長度。

解法的時間、空間複雜度

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

參考資料

花花酱 LeetCode 525. Contiguous Array

花花酱 LeetCode 525. Contiguous Array - 刷题找工作 EP201

贾考博 LeetCode 525. Contiguous Array