D.二分查找-进阶——2389. 和有限的最长子序列

题目链接：2389. 和有限的最长子序列（简单）

算法原理：

解法：二分查找

8ms击败25.52%

时间复杂度O(Nlogn)

①由于 结果数组存的是子序列的最大长度，而不是子序列，所以可以打乱顺序，因此可以排序，进而使用二分

②由于结果数组是nums中 元素之和小于等于queries[i]的长度，所以用到的模型是求最右端点模型

③由于算的是累加和，所以可以用前缀和的思想，排序后求对应前缀和，在找到最右端点后，其下标就是咱们需要的下标

④小细节：最终left和right停留的位置是≤queries[i]的位置，但如果这个位置＞queries[i]则说明left和right一直在第一个位置，且第一个位置就＞queries[i]，符合条件的个数是0

Java代码：

class Solution { public int[] answerQueries(int[] nums, int[] queries) { int n=nums.length,m=queries.length; int[] ret=new int[m];int index=0; //定义前缀和数组 int[] pre=new int[n]; Arrays.sort(nums); pre[0]=nums[0]; for(int i=1;i<n;i++) pre[i]=pre[i-1]+nums[i]; for(int x:queries){ int left=0,right=n-1; //找最右端点 while(left<right){ int mid=left+(right-left+1)/2; if(pre[mid]>x) right=mid-1; else left=mid; } ret[index++]=pre[left]<=x?left+1:0; } return ret; } }