1099.小于K的两数之和

题目描述 (opens new window)

TIP

标签: 数组、双指针、排序

算法思路

这道题目乍一看和 two sum 很像，但是本题中要的值是个在符合条件的前提下，找到一个最大值。

模式识别，在数组中找到两个元素的和：可以使用双指针的思路，有最大的值的考虑，就需要有个变量进行不断赋值比较最终返回结果。

但是本题给定的数组，并不保证顺序，如果想要使用双指针，要保证数组是有序的，所以需要先对给定的数组进行升序排序操作。

我们可以设置两个指针:

• left 指向数组的第一个元素
• right 指向数组的最后一个元素

使用while循环，条件就是题目中给定的条件 左指针要严格小于右指针。

每一次循环，更新下最值，循环完毕之后返回即可

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
//  这道题目使用双指针的算法做比较好
var twoSumLessThanK = function (nums, k) {
  // 首先对数组进行排序
  nums.sort((a, b) => {
    return a - b
  })

  let left = 0
  let right = nums.length - 1
  let sum = -1

  while (left < right) {
    if (nums[left] + nums[right] >= k) {
      right -= 1
    } else {
      sum = Math.max(sum, nums[left] + nums[right])
      left += 1
    }
  }
  return sum
};