和有限的最长子序列【LC2389】
给你一个长度为
n的整数数组nums，和一个长度为m的整数数组queries。返回一个长度为
m的数组answer，其中answer[i]是nums中 元素之和小于等于queries[i]的 子序列 的 最大 长度 。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
真的是简单题？
- 思路：贪心+前缀和+二分查找
- 由于要求寻找小于目标值的子序列的最大长度【全局最优】，因此我们可以优先选择较小的数字【局部最优】
- 又由于要求寻找的是子序列，数组元素可以改变顺序，因此可以将数组从小到大排序
- 然后求出数组元素的前缀和数组，在前缀和数组中搜索小于目标值的最大值对应的下标，即为小于目标值的最长子序列长度
实现
由于前缀和数组可能存在越界，因此可以先记录queries数组的最大值，当前缀和超过该值时，退出循环，记录此时的下标，即为二分查找的右边界
class Solution { public int[] answerQueries(int[] nums, int[] queries) { int m = queries.length, n = nums.length; int[] ans = new int[m]; Arrays.sort(nums); int maxQ = 0; for (int i = 0; i < m; i++){ maxQ = Math.max(maxQ, queries[i]); } int[] sum = new int[n + 1]; int r = n; for (int i = 0; i < n; i++){ if (nums[i] + sum[i] > maxQ) { r = i; break; } sum[i + 1] = nums[i] + sum[i]; } for (int i = 0; i < m; i++){ ans[i] = binarySearch(sum, queries[i], r); } return ans; } public int binarySearch(int[] sum, int target, int r){ int l = 1; while (l <= r){ int mid = (l + r) >> 1; if (sum[mid] <= target){ l = mid + 1; }else{ r = mid - 1; } } return l - 1; } }
