README.md

2389. 和有限的最长子序列

English Version

题目描述

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

 

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

 

提示：

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

解法

方法一：排序 + 前缀和 + 二分查找

将 nums 排序，对于每个 queries[i]，求出 nums 中所有元素之和小于等于 queries[i] 的子序列的最大长度。

时间复杂度 $O((n+m)\times logn)$。其中 $n$ 和 $m$ 分别为 nums 和 queries 的长度。

Python3

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

Java

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

    private int search(int[] s, int v) {
        int left = 1, right = s.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (s[mid] > v) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    }
}

C++

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

Go

func answerQueries(nums []int, queries []int) []int {
	sort.Ints(nums)
	n, m := len(nums), len(queries)
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = s[i] + v
	}
	ans := make([]int, m)
	for i, v := range queries {
		left, right := 1, len(s)
		for left < right {
			mid := (left + right) >> 1
			if s[mid] > v {
				right = mid
			} else {
				left = mid + 1
			}
		}
		ans[i] = left - 1
	}
	return ans
}

TypeScript

function answerQueries(nums: number[], queries: number[]): number[] {
    const n = nums.length;
    nums.sort((a, b) => a - b);
    return queries.map(query => {
        let sum = 0;
        for (let i = 0; i < n; i++) {
            sum += nums[i];
            if (sum > query) {
                return i;
            }
        }
        return n;
    });
}

Rust

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()
    }
}

...