javascript - 数组内 n 个数字的总和是 x 个数字并创建结果的子集

Question

例如，如果您有一个数组 [20, 6, 7, 8, 50]，如果我传递值 21，它应该返回 [6,7,8] 这个子数组。注意:数字之和要有先后顺序。

[20, 6, 7, 8, 50]
21 - [6, 7, 8]
13 - [6, 7]
50 - [] - because it is not in sequence

我试过了，但没用

function sumoftwonumer(arr, s) {
    let hashtable = {}
    let sum = []
    for(let i=0; i<arr.length; i++) {
        let innerRequiredValue = s - arr[i] 
        if(hashtable[innerRequiredValue.toString()] !== undefined) {
            sum.push([arr[i], innerRequiredValue])
        }
        hashtable[innerRequiredValue.toString()] = arr[i]
    }
    console.log(hashtable)
    return sum
}

Answer 1

您可以尝试使用嵌套 for 循环。最坏情况下的时间复杂度将为 O(n^2)。确保看到第二种方法更有效。

let arr = [20, 6, 7, 8, 50]

function findNums(arr,sum){
  let temp = 0;
  for(let i = 0;i<arr.length;i++){
    temp = arr[i];
    for(let j = i+1;j<arr.length;j++){
      temp += arr[j];
      if(temp === sum) return arr.slice(i,j+1);
      if(temp > sum) break;
    }
  }
  return [];
}

console.log(findNums(arr,21))
console.log(findNums(arr,13))
console.log(findNums(arr,50))

更好的解决方案是创建一个变量 temp。开始向其中一个一个地添加元素。当它变得大于给定的总和时，则从数组的开头删除元素。

let arr = [20, 6, 7, 8, 50]

function findNums(arr,sum){
  let temp = arr[0];
  let low = 0;
  for(let i = 1;i<arr.length;i++){
    temp += arr[i];
    if(temp === sum) return arr.slice(low,i+1);
    while(temp > sum){
      temp -= arr[low]
      low++;
    }
  }
  return [];
}

console.log(findNums(arr,21))
console.log(findNums(arr,13))
console.log(findNums(arr,50))

对于负数

负数的问题在于，当 temp(当前总和)变得大于给定总和时，我们无法从开始删除元素，因为我们可能在数组之后有如此多的负数，这可能会使temp 小于或等于总和

对于负数，您需要创建一个对象来跟踪已计算的子数组总和。

let arr = [4,-2,-3,5,1,10]

function findNums(arr,sum){
  let obj = {}
  let temp = 0;
  for(let i = 0;i<arr.length;i++){
    temp += arr[i];
    if(temp === sum) return arr.slice(0,i+1);
    if(obj[temp - sum] != undefined){
      if(obj[temp-sum]+1 !== i){
        return arr.slice(obj[String(temp - sum)]+1,i+1);
      }
    }
    obj[temp] = i;
  }
  return [];
}


console.log(findNums(arr,0))
console.log(findNums(arr,-1))
console.log(findNums(arr,13))
console.log(findNums(arr,1))