這篇是要分享幾個在解一些 LeetCode 問題會用到的演算法，包括 frequency counter、multiple pointers、sliding window 等，並搭配幾個程式問題搭配練習。

Frequency Counter

使用物件去紀錄值或某值發生的頻率，可以避免重複地去遍歷資料。

範例1.

建立一個 same 的函式，input 為兩個陣列，當第一個陣列的所有數字平方後，和第二個陣列的數字出現順序相同，且數字出現頻率也相同。

same([1, 2, 3], [4, 1, 9]); // true
same([1, 2, 3], [1, 9]); // false
same([1, 2, 3], [4, 4, 1]); // false

原本做法會用到 for loop & indexOf，時間複雜度為 O(n^2)

使用 frequency counter:

function same(arr1, arr2) {
  if(arr1.length !== arr2.length) {
    return false;
  }

  let counter1 = {};
  let counter2 = {};
  for(let ele of arr1) {
    counter1[ele] = (counter1[ele] || 0) + 1;
  }

  for(let ele of arr2) {
    counter2[ele] = (counter2[ele] || 0) + 1;
  }

  for(let key in counter1) {
    if(!(key ** 2 in counter2)) {
      return false;
    }
    
    if(counter2[key ** 2] !== counter1[key]) {
      return false;
    }
  }
  return true;
}

範例2. 242. Valid Anagram

若兩個字串皆擁有相同的字母，且出現的次數皆相同，就回傳 true，反之為 false，字母出現的順序不必相同。

解法:

function validAnagram(str1, str2){
  let charCounter = {};
  
  for (const c of str1) {
    // 若 counter 內已有某個字元，就為出現次數 + 1，若無就新增字元並設定為 1
    charCounter[c] = (charCounter[c] || 0) + 1;
  }
  
  for (const c of str2) {
    // 若在另一個字串有出現 str1 出現過的字元，就將次數 - 1，若出現在 str1 沒出現的字元，就設定 false
    charCounter[c] = (charCounter[c] || 0) - 1;
  }
  
  for(let key in charCounter) {
    if(charCounter[key] !== 0) return false;
  }
  
  return true;
}

Multiple Pointers

這個方法是建立多個 pointers 並設定給 pointers 某個索引值，pointers 會隨著程式執行改變索引值到一個陣列的開始、中間或結尾，透過這些 pointers 可以代表當前陣列搜尋到的位置，或是表示範圍。作用是可以有效地降低複雜度。

範例1.

建立一個 sumZero 的函式，input 為一個已經排序好的整數陣列，output 為整數陣列中第一對兩數和為 0 的陣列，若找不到兩數相加為 0，就回傳 undefined。

sumZero([-3, -2, -1, 0, 1, 2, 3]); // [-3, 3]
sumZero([-2, 0, 1, 3]); // undefined
sumZero([1, 2, 3]); // undefined

原本作法使用雙重迴圈可以解決，時間複雜度為 O(n^2)。

使用 multiple pointers:

function sumZero(arr) {
  let left = 0;
  let right = arr.length - 1;
  
  while(left < right) {
    let sum = arr[left] + arr[right];

    if(sum === 0) {
      return [arr[left], arr[right]];
    } else if(sum > 0) {
      right--;
    } else {
      left++;
    }
  }
}

範例2.

建立一個函式 countUniqueValues，input 為一個已經排序好的陣列，output 為陣列內總共出現幾種數字。

countUniqueValues([1, 1, 1, 2]); // 2
countUniqueValues([1, 2, 3, 4, 4, 4, 7, 7, 12, 13]); // 7
countUniqueValues([]); // 0

解法

設定一個 pointer 並記錄初始值為 0，當出現新數字種類時 pointer 加一，同時陣列內在新 pointer 值下的元素值會被新數字所覆寫。

接著使用 for loop 做遍歷，若發現當前遍歷的元素值和 pointer 索引的元素值不同時，表示發現新的數字，pointer 值加一。

function countUniqueValues(arr) {
  if(arr.length) return 0;

  let i = 0;
  for(let j = 1; j < arr.length; j++) {
    if(arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j];
    }
  }
  return i + 1; // index 從 0 開始
}

Sliding Window

使用一個變數儲存一個特定長度的子陣列/字串或是子陣列元素的總和值，並透過移除及新增該變數的開頭或結尾元素，不斷產生和舊陣列只有一個元素不同的新陣列去達成解題的目的。若題目有需要用到子陣列/子字串時，是個不錯的解法。

這篇文章有動畫演示，可以參考閱讀。

範例1.

建立一個函式 maxArrSum，input 為一個存放數字的陣列及一個數字 n，output 為陣列中連續 n 個數字元素相加後最大的總和。

maxArrSum([1, 3, 5, 2, 7, 1], 2); // 9(2+7)
maxArrSum([1, 2, 5, 2, 8, 1, 6], 4); // 17(2+5+2+8)
maxArrSum([4, 2, 1, 6], 1); // 6
maxArrSum([], 1); // null

sliding window 解法:

function maxArrSum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  
  if(arr.length < num) return null;
  for(let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  
  for(let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

範例2. 209. Minimum Size Subarray Sum

function minSubArrayLen(nums, sum) {
  let total = 0;
  let start = 0;
  let end = 0;
  let minLen = Infinity;
    
  while(start < nums.length) {
    if(total < sum) {
      total += nums[end];
      end++;
    } else if(total >= sum) {
      minLen = Math.min(minLen, end - start);
      total -= nums[start];
      start++;
    } else {
      break;
    }
  }
  return minLen === Infinity ? 0 : minLen;
}

範例3. 3. Longest Substring Without Repeating Characters

function findLongestSubstring(str){
  let chars = {};
  let start = 0;
  let length = 0;
  
  for(let i = 0; i < str.length; i++) {
    // if char has been seen before, change start to max of start chars[str[i]] - which holds elem just after it
    // 如果 chars 已經有該字元，代表重複出現，此時重新設定不重覆字串的開始 index
    if(chars[str[i]]) {
      start = Math.max(start, chars[str[i]]);
    }
    
    // 2nd param gives the no of chars btw i and the start position
    // 比對目前最長的長度和新不重複字串的長度
    length = Math.max(length, i - start + 1);
    // point to the next char
    chars[str[i]] = i + 1;
  }
  return length;
}

console.log(findLongestSubstring(''));
console.log(findLongestSubstring('rithmschool'));
console.log(findLongestSubstring('thisisawesome'));
console.log(findLongestSubstring('thecatinthehat'));
console.log(findLongestSubstring('bbbbb'));
console.log(findLongestSubstring('longestsubstring'));
console.log(findLongestSubstring('thisishowwedoit'));

過程圖解可參考: https://yuihuang.com/lc-3/