遍历数组并找到数字范围之间的和

Question

例如，如果我传递数字10和数组[1, 2, 4, 4]函数应该如果数组是[4,2,1,1]函数应返回false，因为总和不在2个数之间。

Answer 1

我会解决它像这样没有递归，只是遍历元素和未来的人，一旦找到一个解退出循环：

function solution(n, arr) { 
 
    if (n < 0) return null; 
 
    if (n === 0) return []; 
 

 
    for (var i = 0; i < arr.length; i++) { 
 
     var first = arr[i]; // first addend 
 
     for (var j = i + 1; j < arr.length; j++) { // considering only next elements in the array 
 
      if (first + arr[j] === n) { 
 
       console.log(`found solution with ${first} and ${arr[j]}`); 
 
       return true; 
 
      } 
 
     } 
 
    } 
 
    console.log('no solution found'); 
 
    return false; 
 
} 
 

 
console.log(solution(8, [4, 3, 45, 2, 5, 3])); 
 
console.log(solution(8, [-1, 2, 3, 4]));

Answer 2

天真执行检查两个数字的总和是嵌套循环，见下面：

function isSumInArray(sum, array) { 
    for (let i=0; i < array.length; i++) { 
     for (let j=0; j < array.length; j++) { 
      if (array[i] + array[j] === sum && i !== j) { 
       return true 
      } 
     } 
    } 
    return false; 
} 

有更好的方法来实现这个，b我选择它是因为我认为这是最简单的理解。你在这里经过两次数组，如果这两个数字等于你想要的总和（并且它们不是数组中的相同数字），则返回true。如果没有任何组合满足此条件，则返回false。

Answer 3

使用#some和#find功能检查，如果任意两个数字的给定数组中的总和等于传递的参数 - 见演示如下：

function solution(num, array) { 
 
    return array.some(function(e, i) { 
 
    return (num - e + array.find(function(c, k) { 
 
     return c == e && i != k 
 
    })) == num; 
 
    }); 
 
} 
 

 

 
console.log(solution(8, [-1, 2, 3, 4]), solution(8, [-1, 4, 3, 4]), solution(8, [4,3,45,2,5,3]));

Answer 4

在阵列中的任何拖数

function test(array , n) 
 
{ 
 
    for(var i=0;i<array.length;i++) 
 
    { 
 
    for(var j=0;j<array.length ; j++) 
 
     if(array[i] + array[j] == n && i != j) 
 
     return true; 
 
    } 
 
    return false; 
 
} 
 

 
var array = [1,2,3,4,2]; 
 
console.log(test(array , 1)); 
 
console.log(test(array , 4));

Answer 5

对于每个元素，您需要对所有其他元素进行“数学运算”以查看它们是否正确相加。

最简单的实现是嵌套循环O（N^2）。

伪代码：

def solution(list, target) 
    for each element e1 in list 
    for each element e2 in list 
     if e2 is e1 
     continue 
     end if 
     if e1 + e2 is target 
     return true 
     end if 
    loop 
    loop 
    return false 
end def 

代码：

function solution(list, target) { 
 
    for(let i = 0; i < list.length; i++) { 
 
     const e1 = list[i]; 
 
     for(let j = 0; j < list.length; j++) { 
 
      const e2 = list[j]; 
 
      if(i === j) { continue; } 
 
      if(e1 + e2 === target) { 
 
       return true; 
 
      } 
 
     } 
 
    } 
 
    return false; 
 
} 
 

 
console.log(solution([1,2,3,4,5], 2));

下一个简单的解决方案是要认识到除（即，求和操作）是可交换的。这意味着操作数的顺序并不重要。 1 + 2与2 + 1相同。这意味着我们不需要重新计算我们已经在外部循环中访问过的数字的总和，因为当我们前进时，我们计算a + b的总和，因此按照定义覆盖b + a。虽然总体复杂性保持不变：O（N^2）（AFAICT）。

伪代码：

def solution(list, target) 
    for each element e1 in list 
    for each element e2 that is to the right of e1 in list 
     if e1 + e2 is target 
     return true 
     end if 
    loop 
    loop 
    return false 
end def 

代码：

function solution(list, target) { 
 
    for(let i = 0; i < list.length; i++) { 
 
     const e1 = list[i]; 
 
     for(let j = i+1; j < list.length; j++) { 
 
      const e2 = list[j]; 
 
      if(e1 + e2 === target) { 
 
       return true; 
 
      } 
 
     } 
 
    } 
 
    return false; 
 
} 
 

 
console.log(solution([1,2,3,4,5], 5));

一个更好的解决方案是将两个事实结合起来，添加是可交换的，我们知道要寻找什么，而不不得不第二次实际枚举列表。即如果a是当前元素，那么我们知道我们想要a + x = target，所以x可以很容易地计算（这是差异）。通过使用O（1）查找数据结构，我们可以替换内部循环，并使算法O（N）整体。

要重新说明问题，列表中的每个元素必须与左侧的所有元素以及右侧的所有元素相加。当我们向外循环前进时，我们对所有右手元素进行求和（因为加法的交换性）。随着循环的进展，元素右侧的所有元素最终都将随着它进行测试。

为了总结左边的所有元素，我们可以用已经看到的元素索引的哈希表替换内部循环。然后我们可以使用这样的事实a + x = target，因此，x = target - a检查散列表中存在x。

伪代码：

def solution(list, target) 
    var hash <- hashtable: [integer:boolean] 
    for each element in list 
    if hash has sum-element 
     return true 
    else 
     add element to hash 
    endif 
    loop 
end def 

代码：

function solution(list, target) { 
 
    const hash = new Set; 
 
    for(let e of list) { 
 
     if(hash.has(target-e)) { 
 
      return true; 
 
     } 
 
     hash.add(e); 
 
    } 
 
    return false; 
 
} 
 

 
solution([1,2,3,4,5], 3);