525. Contiguous Array

15329 ワード
HashMap leetcode テキストリンク

💡 に答える

var findMaxLength = function (nums) {
  let sum = 0;
  let sumArr = [];

  for (let a = 0; a < nums.length; a++) {
    if (nums[a] === 0) nums[a] = -1;
    sum += nums[a];
    sumArr.push(sum);
  }

  let obj = {};
  obj[0] = [-1];

  for (let i = 0; i < sumArr.length; i++) {
    let cur = sumArr[i];
    obj[cur] ? obj[cur].push(i) : (obj[cur] = [i]);
  }
  console.log(sumArr);

  console.table(obj);
  let maxLen = 0;

  for (let [key, value] of Object.entries(obj)) {
    let len = value[value.length - 1] - value[0];
    maxLen = Math.max(maxLen, len);
  }

  console.log(maxLen);

  return maxLen;
};

let nums = [1, 0, 1, 1, 1, 0, 0, 1, 1];
findMaxLength(nums);

📝 結果



📝 整理する


難しいですね.HashMapに関する質問でよく出てくるタイプだそうですが、初めて触れるともっと難しく感じます.
まず,この問題を理解するには,先に解いた2つのSum(リンク:https://velog.io/@ken1204/1.-Two-Sum)の問題を理解する必要がある.この問題の解題方法にはHash Mapを利用した解題方法があり,それを適用した方法である.(リンクを使用して詳細を表示)

  • この問題はnums = [0,1 ...]などの2つの数字(0, 1)を繰り返す.ここで、隣接するサブアレイを見つける必要があり、これは、サブアレイの0と1の個数が同じでなければならないことを意味する.

  • ここでnumsに並ぶ0を全部-1に変えたら?サブアレイの0と1の個数は同じでなければならないため、サブアレイ内のすべての要素の和は0になる.

  • ここではTwo Sum問題の解を適用することができ,すべての要素の和が0であるため,targetを0に設定し,累積和を生成する.
    •   for (let a = 0; a < nums.length; a++) {
    if (nums[a] === 0) nums[a] = -1;
    
    // cumulative sum
    sum += nums[a];
    sumArr.push(sum);
  }

  • cumentative sumとは,上記のコードのように各要素を追加し続ける要素がsumArrとpushである.

  • 例えば、[ 1, 8, 6, 3, 2, 5, 3 ]およびtarget=10の合計積算数があると仮定する.では、上のサブアレイ[3, 2, 5]のすべての要素の和はtarget = 10に等しい.これは、最初のインデックスに対応する1〜5のインデックスの合計から、別のサブアレイ要素1, 8, 6の合計を減算したものに等しい.

  • したがって、アレイのインデックス(3~5)は、元のアレイnumsのサブアレイのインデックスと同じであり、累積和ではない.したがって、本例では、サブアレイの長さは[3,2,5]、すなわち3である.

  • 以上のコードのnums配列の累積和は[ 1, 0, 1, 2, 3, 2, 1, 2, 3 ]である.

  • 次に、sumArr(=累積和)の要素をkeyとして作成し、valueの値のhash mapをインデックスします.
    •   for (let i = 0; i < sumArr.length; i++) {
    let cur = sumArr[i];
    obj[cur] ? obj[cur].push(i) : (obj[cur] = [i]);
  }
  • では、サブアレイが最初から始まる例外を考慮する必要がある.ここでは、要素0とインデックスを-1に設定する.
    • obj[0] = [-1];
    このコースが完了すると、
  • には次のものが含まれます.

  • であり、現在、サブアレイの最大長を求めるのは難しくない.
    •  for (let [key, value] of Object.entries(obj)) {
    let len = value[value.length - 1] - value[0];
    maxLen = Math.max(maxLen, len);
  }

  console.log(maxLen);

  return maxLen;
    上記のコード
  • に示すように、obj毎のkeyの値は、各valueのアレイが昇順で配列されているため、最後尾の値と最前面の値とを互いに減算し、各valueを比較するアレイ形式で格納される.最大価格がkeyなら、それが答えです.
    • 修正、指摘を歓迎します!

    質問リンク


    https://leetcode.com/problems/contiguous-array/

    LeetCode GitHub


    https://github.com/tTab1204/LeetCode
    C#でReportファイルを直接印刷(rdlc)
    [プログラマー]ロックとキー