【算法】和为K的连续子数组

牛客链接：https://www.nowcoder.com/practice/704c8388a82e42e58b7f5751ec943a11?tpId=196&&tqId=37127&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total/question-ranking

使用【前缀法】，把所有连续和合索引存进哈希表，当sum-k存在时证明存在连续的子数组和尾k。

function maxlenEqualK(arr, k) {
  // write code here
  let sum = 0;
  const map = new Map();
  let len = 0;
  map.set(0, -1);
  for (let i in arr) {
    sum += arr[i];
    if (!map.has(sum)) {
      map.set(sum, i);
    }
    if (map.has(sum - k)) {
      console.log("i", i, "map.get(sum-k)", map.get(sum - k));
      len = Math.max(len, i - map.get(sum - k));
    }
  }
  return len;
}

以下暴力解法会超时！！！！！

function solution(arr, k) {
  let maxLen = 0;
  for (let i = 0; i < arr.length; i++) {
    let count = arr[i];
    if (count === k) {
      maxLen = Math.max(maxLen, 1);
    }
    for (let j = i + 1; j < arr.length; j++) {
      count += arr[j];
      if (count === k) {
        maxLen = Math.max(maxLen, j - i + 1);
      }
    }
  }
  return maxLen;
}

const arr3 = [-1, 0, 0, 0];
const k3 = -1;
const arr1 = [1, -2, 1, 1, 1];
const k1 = 0;
const arr2 = [0, 1, 2, 3];
const k2 = 3;
const arr4 = [1, 1, 1];
const k4 = 2;
console.log(solution(arr4, k4));
// [1,-2,1,1,1],0   =>3  [0,1,2,3] 3 =>3  [-1,0,0,0] -1 => 4