例如，如果你有一个数组 [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(当前总和)大于给定的总和时，我们无法从 start 中删除元素，因为我们在数组中可能有负数，这可能会使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))一种可能性，取决于你想如何使用它，是按照你的尝试去做，创建一个部分和的哈希图，返回一个函数，该函数将在该哈希图中查找你的值。 在这里，我这样做，使函数变得柯里，这样你就不必在每次调用时都为一组数字创建哈希图。
初始调用是O(n^2)，但后续调用只是O(1)。 如果要在同一组数字上搜索多个值，则此样式很有用。 如果您只有一个值要搜索，那么像Maheer Ali答案中的第二个技术会更有效。
const range = (lo, hi) => [...Array (hi - lo) ]
.map ( (_, i) => lo + i )
const sum = (nbrs) =>
nbrs .reduce ( (a, b) => a + b, 0 )
const findSequentialSum = (nbrs) => {
const subtotals = range (0, nbrs .length)
.flatMap (
i => range (i + 2, nbrs .length + 1)
.map (j => nbrs .slice (i, j) )
)
// .reduce((a, b) => a.concat(b), [[]])
.reduce (
(a, sub, _, __, tot = sum(sub) ) => ({
...a,
[tot]: a [tot] || sub
}),
{}
)
return (total) => subtotals [total] || []
}
const nbrs = [20, 6, 7, 8, 50]
const search = findSequentialSum (nbrs)
console .log (
search (21), //~> [6, 7, 8]
search (13), //~> [6, 7]
search (50), //~> []
)两个帮助程序函数应该很简单：range(3, 10) //=> [3, 4, 5, 6, 7, 8, 9]和sum([2, 5, 10]) //=> 17
如果flatMap在您的环境中不可用，则可以替换
.flatMap (
i => range (i + 2, nbrs .length + 1)
.map (j => nbrs .slice (i, j) )
)
跟
.map (
i => range (i + 2, nbrs .length + 1)
.map (j => nbrs .slice (i, j) )
)
.reduce((a, b) => a.concat(b), [[]])
另外，这里的2
i => range (i + 2, nbrs .length + 1)
要求序列长度至少为两个条目。 如果你想让50返回[50](这对我来说似乎更合乎逻辑)，那么你可以用1替换该2。 或者你可以用更大的东西替换它，如果你只想找到长度为 5 或更多的子序列。
最后，如果你想返回添加到总数中的所有子序列，这将是一个简单的修改，替换：
[tot]: a [tot] || sub
跟
[tot]: (a [tot] || []).concat([sub])