【排序, 前缀和, 二分查找】和有限的最长子序列

题目

6160. 和有限的最长子序列

---

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

示例 1：

输入：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 。

示例 2：

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

提示：

• n == nums.length
• m == queries.length
• 1 <= n, m <= 1000
• 1 <= nums[i], queries[i] <= 10^6

解题

方法一：排序 前缀和 二分查找

思路

首先，要求的是子序列的最大长度，因为子序列可以通过增删元素得到，也就意味着数组可以排序，而子序列的最大长度又与子序列的和有关，所以应该先把数组升序排序。

然后问题就变成了求 nums 中元素之和小于等于 queries[i] 的前缀子数组的最大长度，这里提到了子数组元素之和，自然可以想到用前缀和求解，于是构造数组的前缀和数组。

那么问题就变成了求**前缀和数组**中小于等于 queries[i] 的元素中最靠右的位置。在有序数组中求元素位置可以使用二分查找进行优化，具体需要用到：二分查找 - 整数二分 - 小于等于。

求出位置后覆盖 queries 数组最后返回即可。

代码

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] prefixSums = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            prefixSums[i] = nums[i - 1] + prefixSums[i - 1];
        }
        for (int i = 0; i < queries.length; ++i) {
            int query = queries[i];
            int l = 0, r = n;
            while (l < r) {
                int c = l + r + 1 >> 1;
                if (prefixSums[c] <= query) l = c;
                else r = c - 1;
            }
            queries[i] = l;
        }
        return queries;
    }
}

std::upper_bound

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> prefix_sums(n + 1);
        for (int i = 0; i < n; ++i) {
            prefix_sums[i + 1] = prefix_sums[i] + nums[i];
        }
        for (int& query : queries) {
            query = upper_bound(prefix_sums.begin(), prefix_sums.end(), query)- prefix_sums.begin() - 1;
        }
        return queries;
    }
};