给出两个整数阵列查找所有等于给定目标编号的总和的子阵列

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。

希望这是有用的。