給出兩個整數陣列查找所有等於給定目標編號的總和的子陣列

Question

給出兩個整數陣列查找其總和等於給定目標編號的所有子陣列。例如。 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。

希望這是有用的。