2つの整数配列を与える合計が与えられたターゲット番号に等しいサブアレイを見つける

Question

2つの整数配列を与えると、合計が与えられたターゲット番号に等しいすべてのサブ配列を見つける。例えば。 array1 = [1,2,3,4] array2 = [7,3,4] sumToFind = 5 findSubArrays（array1、array2、num） 出力：[[1,4]、[2,3]]

私は以下のようにアプローチしましたが、O（N2）の複雑さを持つため、O（N）を達成するために改善することができます。

function findSubArray(array1, array2, sumToFind){ 
    var len1 = array1.length; 
    var len2 = array2.length; 
    var result=[]; 
    for(var i=0;i<len1;i++){ 
    for(var j=0;j<len2;j++){ 
     if(array1[i] + array2[j] === sumToFind){ 
      result.push([array1[i], array2[j]]); 
     } 
    } 
    } 
    return result; 
} 

Answer 1

私は、これはO（N）を達成できることを確認していないが、私は解決策は、（ソートアルゴリズムの時間複雑である）O（nlgn）の複雑さを持っていました。

var findSubArray2 = function(arr1, arr2, sumToFind) { 
    var result = []; 
    var sortedArr1 = arr1.sort(); // O(nlgn) 
    var sortedArr2 = arr2.sort(); // O(mlgm) 

    // Use two pointers to check element in each array. 
    // O(n + m) 
    for (var i = 0, j = arr2.length - 1; i < arr1.length && j >= 0;) { 
    var temp = sortedArr1[i] + sortedArr2[j]; 
    if (temp > sumToFind) { 
     j--; 
    } else if (temp < sumToFind) { 
     i++; 
    } else { 
     result.push([sortedArr1[i], sortedArr2[j]]); 
     i++; 
    } 
    } 

    return result; 
} 

注1：あなたのarray1とarray2は、配列をソートしている場合、それはO（M + N）である可能性があります。

注2：どのアルゴリズムがデフォルトのsortメソッドが実装されているかはわかりませんが、O（N2）とは思われません。 hereを参照してください。

希望すると便利です。