Question

2389. Longest Subsequence With Limited Sum

中文文档

Description

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 elements is less than or equal to _queries[i].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: We answer the queries as follows:
- 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.
- 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.
- 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.

Example 2:

Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

 

Constraints:

• n == nums.length
• m == queries.length
• 1 <= n, m <= 1000
• 1 <= nums[i], queries[i] <= 106

Solutions

Solution 1

class Solution:
  def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
    nums.sort()
    s = list(accumulate(nums))
    return [bisect_right(s, q) for q in queries]

class Solution {
  public int[] answerQueries(int[] nums, int[] queries) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; ++i) {
      nums[i] += nums[i - 1];
    }
    int m = queries.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      ans[i] = search(nums, queries[i]);
    }
    return ans;
  }

  private int search(int[] nums, int x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
    sort(nums.begin(), nums.end());
    for (int i = 1; i < nums.size(); i++) {
      nums[i] += nums[i - 1];
    }
    vector<int> ans;
    for (auto& q : queries) {
      ans.push_back(upper_bound(nums.begin(), nums.end(), q) - nums.begin());
    }
    return ans;
  }
};

func answerQueries(nums []int, queries []int) (ans []int) {
  sort.Ints(nums)
  for i := 1; i < len(nums); i++ {
    nums[i] += nums[i-1]
  }
  for _, q := range queries {
    ans = append(ans, sort.SearchInts(nums, q+1))
  }
  return
}

function answerQueries(nums: number[], queries: number[]): number[] {
  nums.sort((a, b) => a - b);
  for (let i = 1; i < nums.length; i++) {
    nums[i] += nums[i - 1];
  }
  const ans: number[] = [];
  const search = (nums: number[], x: number) => {
    let l = 0;
    let r = nums.length;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (nums[mid] > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  for (const q of queries) {
    ans.push(search(nums, q));
  }
  return ans;
}

impl Solution {
  pub fn answer_queries(mut nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    nums.sort();
    queries
      .into_iter()
      .map(|query| {
        let mut sum = 0;
        for i in 0..n {
          sum += nums[i];
          if sum > query {
            return i as i32;
          }
        }
        n as i32
      })
      .collect()
  }
}

public class Solution {
  public int[] AnswerQueries(int[] nums, int[] queries) {
    int[] result = new int[queries.Length];
    Array.Sort(nums);
    for (int i = 0; i < queries.Length; i++) {
      result[i] = getSubsequent(nums, queries[i]);
    }
    return result;

  }

  public int getSubsequent(int[] nums,int query) {
    int sum = 0;
    for (int i = 0; i < nums.Length; i++) {
      sum += nums[i];
      if (sum > query) {
        return i;
      }
    }
    return nums.Length;
  }
}

Solution 2

class Solution:
  def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
    nums.sort()
    m = len(queries)
    ans = [0] * m
    idx = sorted(range(m), key=lambda i: queries[i])
    s = j = 0
    for i in idx:
      while j < len(nums) and s + nums[j] <= queries[i]:
        s += nums[j]
        j += 1
      ans[i] = j
    return ans

class Solution {
  public int[] answerQueries(int[] nums, int[] queries) {
    Arrays.sort(nums);
    int m = queries.length;
    Integer[] idx = new Integer[m];
    for (int i = 0; i < m; ++i) {
      idx[i] = i;
    }
    Arrays.sort(idx, (i, j) -> queries[i] - queries[j]);
    int[] ans = new int[m];
    int s = 0, j = 0;
    for (int i : idx) {
      while (j < nums.length && s + nums[j] <= queries[i]) {
        s += nums[j++];
      }
      ans[i] = j;
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
    sort(nums.begin(), nums.end());
    int m = queries.size();
    vector<int> idx(m);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) {
      return queries[i] < queries[j];
    });
    vector<int> ans(m);
    int s = 0, j = 0;
    for (int i : idx) {
      while (j < nums.size() && s + nums[j] <= queries[i]) {
        s += nums[j++];
      }
      ans[i] = j;
    }
    return ans;
  }
};

func answerQueries(nums []int, queries []int) (ans []int) {
  sort.Ints(nums)
  m := len(queries)
  idx := make([]int, m)
  for i := range idx {
    idx[i] = i
  }
  sort.Slice(idx, func(i, j int) bool { return queries[idx[i]] < queries[idx[j]] })
  ans = make([]int, m)
  s, j := 0, 0
  for _, i := range idx {
    for j < len(nums) && s+nums[j] <= queries[i] {
      s += nums[j]
      j++
    }
    ans[i] = j
  }
  return
}

function answerQueries(nums: number[], queries: number[]): number[] {
  nums.sort((a, b) => a - b);
  const m = queries.length;
  const idx: number[] = new Array(m);
  for (let i = 0; i < m; i++) {
    idx[i] = i;
  }
  idx.sort((i, j) => queries[i] - queries[j]);
  const ans: number[] = new Array(m);
  let s = 0;
  let j = 0;
  for (const i of idx) {
    while (j < nums.length && s + nums[j] <= queries[i]) {
      s += nums[j++];
    }
    ans[i] = j;
  }
  return ans;
}