和为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的两个数字
 */

/**
 * 利用双指针
 */
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是递增的
 * 利用二分查找
 */
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来存放数据，便于查找
 */
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 []
}

/**
 * 暴力方案
 */
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 []
}

const testArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

console.log(findNumbersWithSumOne(testArr, 21))
console.log(findNumbersWithSumTwo(testArr, 21))
console.log(findNumbersWithSumThree(testArr, 21))
console.log(findNumbersWithSumFour(testArr, 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 []
}