1497. Check If Array Pairs Are Divisible by k

harry xie
2024-10-02 00:37:47

解題程式碼

var canArrange = function (arr, k) {
  const remainMap = new Map();

  for (let i = 0; i < arr.length; i++) {
    let remain = ((arr[i] % k) + k) % k;
    remainMap.set(remain, (remainMap.get(remain) || 0) + 1);
  }

  for (let i = 1; i <= Math.floor(k / 2); i++) {
    if ((remainMap.get(i) ?? 0) !== (remainMap.get(k - i) ?? 0)) return false;
  }

  return (remainMap.get(0) ?? 0) % 2 === 0;
};

解題思路演算法

留意一些測資:

arr = [0,3]k = 6
arr = [-1,1,-2,2,-3,3,-4,4]k = 3
arr = [2,2,2,2,2,2]k = 3

可以先把除以 k 後的餘數都存到 hashMap 裡面，接著第二次迴圈時我們找出所有可能兩個數相加後等於 k 的組合，

若發現數字 i 和 k - i 出現的次數不同，則代表無法組出題目要的 pair(每個 pair 的 sum 要可以被 k 整除)，

另外根據提示，留意 i === k - i 和 i === 0 的 case:

i === k - i 在更精簡的解法可以不用考慮，

i === 0 的 case，若 0 出現奇數個，代表最後會剩下一個 0 無法配對，回傳 false

解法的時間空間複雜度

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

參考資料