遍歷數組並找到數字範圍之間的和

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);