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 len = nums.length; int[] presum = new int[len]; presum[0] = nums[0]; for (int i = 1; i < len; i++) { presum[i] = presum[i - 1] + 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 + 1; } 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; } }
标签:Limited,nums,int,Sum,subsequence,Subsequence,queries,answer,length From: https://www.cnblogs.com/cnoodle/p/17003858.html