例如,如果您有一个数组 [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
}
最佳答案
您可以尝试使用嵌套 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))
关于javascript - 数组内 n 个数字的总和是 x 个数字并创建结果的子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56133502/