Give two integer Arrays find all subarrays whose sum equal a given target number

Question

Give two integer Arrays find all subarrays whose sum equal a given target number. eg. array1 = [1,2,3,4] array2 = [7,3,4] sumToFind = 5 findSubArrays (array1, array2, num) Output : [[1,4],[2,3]]

I approached it in following way, but since it has a complexity of O(N2) can it be improved to achieve 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;
}

I'm voting to close this question as off-topic because it's asking how to optimize code that already works. — Josh Beam, Jul 07 '16 at 22:52

score 0 · Accepted Answer · edited May 23 '17 at 12:22

I am not sure this could achieve O(N), but I got a solution has a complexity of O(nlgn) (which is the sort algorithm time complexity).

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

Note1: If your array1 and array2 are sorted array, it could be O(m + n).

Note2: Not sure which algorithm the default sort method is implemented, but I don't think is will be O(N2). See here.

Hope this is useful.

Give two integer Arrays find all subarrays whose sum equal a given target number

1 Answers1