时间戳

首页 > 解决方案 > 避免使用嵌套循环来查找数组的最大子字符串？

javascript - 避免使用嵌套循环来查找数组的最大子字符串？

问题描述

应返回根据输入长度添加的最大数量。

例如，如果长度是, ,2中的最大值arr[0] + arr[1]，则应返回。arr[1] + arr[2]arr[2] + arr[3]

输入是数组和长度。

我在一次真正的工作面试中解决了这个问题，但我认为会有一种不使用嵌套循环的方法。

const add = (arr, len) => {
  let rtnVal = 0

  for (let i = len - 1; i < arr.length; i++) {
    let temp_idx = i;
    let temp_sum = 0;
    for (let j = 0; j < len; j++) {
      temp_sum = (temp_sum || 0) + arr[temp_idx]
      temp_idx -= 1
    }

    if (temp_sum > rtnVal) {
      rtnVal = temp_sum
    }
  }

  return rtnVal
}

console.log(add([1, 2, 3, 4, 5, 6, 7, 8, 9], 4))

我希望输出 30

// enhanced nested loop

const add = (arr, len) => {
  let rtnVal = 0;
  for(let i=len-1;i<arr.length;i++){
    let sum = 0
    for(let j=i;j>=i-len+1;j--){
      sum += arr[j]
    }
    if (sum > rtnVal) rtnVal = sum
  }
  return rtnVal

}
console.log(add([9, 9, 9, 4, 5, 6, 7, 8, 9], 3))

标签： javascript

解决方案

使用移动窗口。len从头开始将数字相加。然后继续通过数组添加下一个数字并减去尾随数字。

const add = (arr, len) => {
  return arr.reduce((a,v,i,arr) => {
    a.running += v;
    if(i >= len) {
      a.running -= arr[i-len];
    }
    if(i+1 >= len && a.largest < a.running) {
      a.largest = a.running;
    }
    return a;
  }, {
    largest: Number.NEGATIVE_INFINITY,
    running: 0
  }).largest;
}

console.log(add([1,2,3,4,5,6,7,8,9],4)); // 30
console.log(add([-1,-1,-1,-1],2)); // -2
console.log(add([1],1)); // 1

推荐阅读