2023-03-17 LeetCode：2389. 和有限的最长

2389. 和有限的最长子序列

问题描述

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

示例

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

解题思路

*核心思路：贪心+前缀和+二分查找

1. 先对nums进行排序，排序后计算前缀和；
2. 遍历queries，用二分查找从前缀和数组中找到符合的最大长度；注意，如果找不到，最长长度应该为0。

代码示例（JAVA）

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        // 贪心，先对nums进行排序，排序后计算前缀和
        Arrays.sort(nums);
        int[] preSum = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            preSum[i] = (i >= 1 ? preSum[i - 1] : 0) + nums[i];
        }

        // 二分查找，找到满足条件的最大长度     
        int[] answers = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            answers[i] = search(preSum, queries[i]) + 1;
        }
        return answers;
    }

    public int search(int[] array, int target) {
        if (array[0] > target) {
            return -1;
        }
        int left = 0, right = array.length - 1;
        while (left < right) {
            int mid = right - (right - left) / 2;
            if (array[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

时间复杂度：O(n logn + m log n)