和为S的两个数字

输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

刷题思路

一些基本数学知识：

根据x+y=sum 求xy最小由于array是递增的，则x 、y 距离越远 xy值越小，x y距离越近xy值越大
x+y=(x+m)+(y-m)=sum 假设x是左边元素，y是右边元素即：y>x
可以理解乘积(x+m)(y-m)=xy-(y-x)*m-m^2 其中y-x>0 m^2
所以m值越大，其实(x+m)(y-m)越小，也就是x与y间隔也大 xy越小，由于array是递增的，所以只需要找到第一个满足和为sum的即可

基于这样的特性，有以下方案

方案一：

利用双指针left 、 right
逐步向左、向右逼近

方案二：

利用二分查找

方案三：

利用Map存储已有元素

方案四：

直接暴力解法

代码实现

/**
 * 【中等】和为S的两个数字
 */

/**
 * 利用双指针
 * @param array
 * @param sum
 * @returns {*[]}
 */
function findNumbersWithSumOne(array, sum) {
  let left = 0; let right = array.length - 1
  while (left < right) {
    if (array[left] + array[right] === sum) {
      // 第一个就返回
      return [array[left], array[right]]
    }
    else if (array[left] + array[right] > sum) {
      // 向左逼近
      right--
    }
    else {
      // 向右逼近
      left++
    }
  }
  return []
}

/**
 * 注意数组array是递增的
 * 利用二分查找
 * @param array
 * @param sum
 * @returns {*[]}
 */
function findNumbersWithSumTwo(array, sum) {
  let left = 0
  let right = array.length - 1
  // 将最小值标记设置成最大
  let min = array[right] * array[right]
  let result = []
  while (left < right) {
    if (array[left] + array[right] === sum) {
      // 符合条件
      if (min > array[left] * array[right]) {
        // 最小值
        min = array[left] * array[right]
        result = [array[left], array[right]]
      }
      left++
      right--
    }
    else if (array[left] + array[right] < sum) {
      // 左边向右逼近
      left++
    }
    else {
      // 右边向左逼近
      right--
    }
  }
  return result
}

/**
 * 利用map来存放数据，便于查找
 * @param array
 * @param sum
 */
function findNumbersWithSumThree(array, sum) {
  const resultMap = new Map()
  for (const a of array) {
    resultMap.set(a, true)
  }
  for (const a of array) {
    if (resultMap.has(sum - a)) {
      return [a, sum - a]
    }
  }
  return []
}

/**
 * 暴力方案
 * @param array
 * @param sum
 */
function findNumbersWithSumFour(array, sum) {
  const len = array.length
  for (let index = 0; index < len; index++) {
    const firstValue = array[index]
    for (let j = index + 1; j < len; j++) {
      if (array[j] === sum - firstValue) {
        return [firstValue, array[j]]
      }
    }
  }
  return []
}

console.log(findNumbersWithSumOne([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], 21))
console.log(findNumbersWithSumTwo([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], 21))
console.log(findNumbersWithSumThree([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], 21))
console.log(findNumbersWithSumFour([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], 21))

一些建议

了解二分(折半)查找的原理
熟练掌握Map数据结构的一些api方案
有时候暴力方案比较直接，存在较大优化空间

双指针模型：

function FindNumbersWithSum(array, sum) {
  let left = 0
  let right = array.length - 1
  while (left < right) {
    if (array[left] + array[right] > sum) {
      right--
    }
    else if (array[left] + array[right] < sum) {
      left++
    }
    else {
      return [array[left], array[right]]
    }
  }
  return []
}

和为S的两个数字

和为S的两个数字

题目链接

题目描述

刷题思路

代码实现

一些建议