每日一题 5.8

2389 和有限的最长子序列思路:首先理解题目就是要求nums序列元素和小于等于queries[i]的最长子序列,我一开始的想法是,封装一个函数,他内部是一个定一端的”滑动窗口”,每次加入新元素的时候进行判断,符合就继续循环,超过queries[i]就退出循环,返回当前的右边界对应的下标代码如下:public int[] answerQueries(int[] nums, int[] queries) { Arrays.sort(nums); int[] ans new int[queries.length]; for(int i 0;iqueries.length;i){ ans[i] find(nums,queries[i]); } return ans; } private int find(int [] nums,int target){ int right 0; int i 0; int sum 0; while(right nums.length-1){ if(sum nums[i] target){ sum nums[i]; right; i; }else{ break; } } return right; }那么后续对于这道题进一步的思考,其实可以用二分查找优化,我们将原本的nums数组对应下标的数字改为对应的前缀和即可,就是省略了我们原本方法的函数功能怎么改呢,写一个从1开始的for循环,对每个nums[i]都加上nums[i-1],这样循环下去就能得到一个新的前缀和数组,此时就满足我们很经典的二分查找条件,这里要注意,由于我们要的是小于等于queries[i]的前缀和,所以我们right移动条件应该是大于目标值,让left停留在大于target的位置,这样返回的left就是我们的最大子序列长度代码:public int[] answerQueries(int[] nums, int[] queries) { Arrays.sort(nums); for(int i 1;inums.length; i){ nums[i] nums[i-1]; } int[] ans new int[queries.length]; for(int i 0; iqueries.length; i){ ans[i] find(nums,queries[i]); } return ans; } private int find(int [] nums,int target){ int left 0; int right nums.length - 1; while(left right){ int mid left (right - left)/2; if(nums[mid] target){ right mid - 1; }else{ left mid 1; } } return left; }