寻找数组中和为定值的两个数

最近碰到这样一个问题，输入一个已排序的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字，要将所有的组合列出来。

拿到这个问题，我第一时间想到的方法是用双重 for 循环遍历数组，穷举出所有的组合，判断是否等于目标值。

方法一

for (let i = 0; i < array.length - 1; i++) {  
  for (let j = i + 1; j < array.length; j++) {  
    if(a[i] + a[j] === sum) {
      ...
    }    
  }    
}

这种方法是能解决这个问题的，但是时间复杂度是 O(N^2)，那么有没有效率更高的方法呢？

既然要查找使 a + b = sum 的所有情况，我们可以遍历整个数组，去查找 sum - a，那么现在问题变为在一个数组中去查找一个给定的数，而数组是经过排序的，我们很自然的想到了二分搜索。

方法二

const arr = [1,2,4,6,7,9,10]
const sum = 8

function twoSum (arr, sum) {
  const result = []
  for (let i = 0, len = arr.length; i < len; i++) {
    const index = binarySearch(arr, sum - arr[i])
    if (index !== -1 && i !== index) {
      result.push([arr[i], sum - arr[i]])
      arr.splice(index, 1)
    }
  }
  return result
}

function binarySearch(arr, value) {
  let startIndex = 0,
      stopIndex = arr.length - 1,
      middle = Math.floor((stopIndex + startIndex) / 2);

  while (arr[middle] != value && startIndex < stopIndex) {
    if (value < arr[middle]) {
      stopIndex = middle - 1;
    } else {
      startIndex = middle + 1;
    }
    middle = Math.floor((stopIndex + startIndex) / 2);
  }

  return (arr[middle] !== value) ? -1 : middle;
}

twoSum(arr, sum)

这种方法只用了一次 for 循环，二分搜索的时间复杂度是 O(logN)，所以整个方法的时间复杂度是 O(NlogN)，比第一种方法效率更高。

那么问题来了，这是效率最高的方法吗？能不能只循环一次数组就找到所有组合呢，这样时间复杂度就是 O(N)。用两个指针 i 和 j，各自指向数组的首尾两端，令 i = 0，j = n - 1，然后 i++，j--，逐次判断 a[i] + a[j] === sum。

方法三

const arr = [1,2,4,6,7,9,10]
const sum = 8

function twoSum (arr, sum) {
  const result = []
  let i = 0
      j = arr.length - 1
  
  while (i < j) {
    if (arr[i] + arr[j] > sum) {
      j--
    } else if (arr[i] + arr[j] < sum) {
      i++
    } else {
      result.push([arr[i], arr[j]])
      i++
      j--
    }
  }
  return result
}

twoSum(arr, sum)

随着我们的不断优化，解决方法的时间复杂度由 O(N^2) 变为 O(N)。

接下来我们扩展一下，如果在数组中查找三个数，使得它们的和等于目标值，该怎么解决。这里增加了一个变量，两个数的情况我们是查找 sum - a，三个数我们可以看成是在除去 a 的数组中查找两个数使得 b + c = sum - a，这样一来问题就降维成两个数的情况。

const arr = [1,2,4,6,7,9,10]
const sum = 12

function twoSum (arr, sum, el) {
  const result = []
  let i = 0
      j = arr.length - 1
  
  while (i < j) {
    if (arr[i] + arr[j] > sum) {
      j--
    } else if (arr[i] + arr[j] < sum) {
      i++
    } else {
      result.push([el, arr[i], arr[j]])
      i++
      j--
    }
  }
  return result
}

function threeSum (arr, sum) {
  let result = []
  for (let i = 0, len = arr.length; i < len; i++) {
    const newArr = arr.slice(i + 1)
    result = result.concat(twoSum(newArr, sum - arr[i], arr[i]))
  }
  return result
}

threeSum(arr, sum)

以上是对我这个问题的一些思考，各位读者如果有更简洁的方法，欢迎在评论区当中给出。