[LeetCode] 2389. Longest Subsequence With Limited Sum

You are given an integer array nums of length n, and an integer array queries of length m.

Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:
Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: We answer the queries as follows:

• The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
• The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
• The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.

Example 2:
Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

Constraints:
n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 106

和有限的最长子序列。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-subsequence-with-limited-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题很好，虽然是简单题，但是考察了多个知识点，我这里提供一个排序 + 前缀和 + 二分的思路。

这道题问的满足条件的最长子序列的长度，但是这里的条件是子序列的和 <= target。因为找的是子序列 subsequence 的和，意味着满足条件的子序列中的元素可以不连续，既然不连续，那么也就意味着我们可以对 input 数组进行排序。排序的作用是为了之后我们可以开辟一个额外数组记录前缀和。所以这里我们先对 input 数组作排序和记录前缀和两项操作。

此时我们会得到一个前缀和数组 presum，注意这个数组中的元素是有序的，所以此时我们可以用二分法找到满足 <= queries[i] 的 index。

以后记得看到子序列，也许是可以排序的，因为子序列不在意元素的相对顺序。

复杂度

时间O(nlogn) - O(n) 扫描 queries 数组，O(logn) 用二分法找到每个 query 的位置
空间O(n) - prefix sum array

代码

Java实现

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] presum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            presum[i + 1] = presum[i] + nums[i];
        }

        int m = queries.length;
        int[] res = new int[m];
        for (int i = 0; i < m; i++) {
            int j = helper(presum, queries[i]);
            res[i] = j;
        }
        return res;
    }

    private int helper(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}