{"id":9791,"date":"2022-09-01T05:04:07","date_gmt":"2022-09-01T12:04:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9791"},"modified":"2022-09-01T10:55:39","modified_gmt":"2022-09-01T17:55:39","slug":"leetcode-2389-longest-subsequence-with-limited-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-2389-longest-subsequence-with-limited-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2389. Longest Subsequence With Limited Sum"},"content":{"rendered":"\n

You are given an integer array nums<\/code> of length n<\/code>, and an integer array queries<\/code> of length m<\/code>.<\/p>\n\n\n\n

Return an array <\/em>answer<\/code> of length <\/em>m<\/code> where <\/em>answer[i]<\/code> is the maximum<\/strong> size of a subsequence<\/strong> that you can take from <\/em>nums<\/code> such that the sum<\/strong> of its elements is less than or equal to <\/em>queries[i]<\/code>.<\/p>\n\n\n\n

A subsequence<\/strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [4,5,2,1], queries = [3,10,21]\nOutput:<\/strong> [2,3,4]\nExplanation:<\/strong> We answer the queries as follows:\n- 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.\n- 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.\n- 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.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [2,3,4,5], queries = [1]\nOutput:<\/strong> [0]\nExplanation:<\/strong> The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == nums.length<\/code><\/li>
  • m == queries.length<\/code><\/li>
  • 1 <= n, m <= 1000<\/code><\/li>
  • 1 <= nums[i], queries[i] <= 106<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Sort + PrefixSum + Binary Search<\/strong><\/h2>\n\n\n\n
    Time complexity: O(nlogn + mlogn)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector answerQueries(vector& nums, vector& queries) {    \n    sort(begin(nums), end(nums));\n    partial_sum(begin(nums), end(nums), begin(nums));\n    vector ans;\n    for (int q : queries)\n      ans.push_back(upper_bound(begin(nums), end(nums), q) - begin(nums));\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,222,62],"class_list":["post-9791","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-easy","tag-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9791","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9791"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9791\/revisions"}],"predecessor-version":[{"id":9795,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9791\/revisions\/9795"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9791"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9791"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9791"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}