2389. Longest Subsequence With Limited Sum

注意⚠️ ：数字的子序列是可以排序的

给你一个数组，让你算这个数组里面最小的 3 个数的和。这个数组是 [1,2,3,4,5] 还是 [5,4,3,2,1] 还是别的顺序，影响答案吗？不影响，我们总是可以把数组排序然后取前 3 个数的和。

对nums进行排序，取得前缀和，这样就能在前缀和上使用二分查找：找到大于 queries[i] 的第一个数的下标，由于下标是从 0 开始的，这个数的下标正好就是前缀和小于等于 queries[i] 的最长前缀的长度。

const binarySearch = (left: number, right: number, target: number, arr: Array<number>): number => {
  while (left < right) {
    const mid: number = Math.floor((left + right) / 2)
    if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid
    }
  }
  return right
}

function answerQueries(nums: number[], queries: number[]): number[] {
  // 前缀和 + 二分
  nums.sort((a, b) => a - b)

  for (let i = 0; i < nums.length; i++) {
    if (i > 0) {
      nums[i] += nums[i - 1]
    }
  }

  queries.forEach((item, idx, arr) => {
    arr[idx] = binarySearch(0, nums.length, item + 1, nums)
  })
  return queries
}