和有限的最长子序列【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;}
  }
  

  • 复杂度
    • 时间复杂度：O(mlogn+nlogn)O(mlogn + nlogn)O(mlogn+nlogn)，求取答案需要mmm次二分查找，时间复杂度为O(mlogn)O(mlogn)O(mlogn)，排序所需要的时间复杂度为O(nlogn)O(nlogn)O(nlogn)
    • 空间复杂度：O(n)O(n)O(n)，前缀和数组的空间复杂度