Easy

题目描述

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

返回一个长度为 m 的数组 answer，其中 answer[i] 是你可以从 nums 中选择的子序列的最大长度，使得其元素的和小于或等于 queries[i]。

子序列是由删除某些元素（也可以不删除任何元素）后得到的数组，且不改变剩余元素的相对顺序。

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：我们按如下方式回答查询：
- 子序列 [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] <= 10^6

解题思路

这道题的核心思想是贪心算法。为了让子序列尽可能长，我们应该优先选择较小的元素。

解题思路：

  1. 贪心策略：由于子序列不要求保持原数组的相对顺序，我们可以对原数组进行排序，然后贪心地选择最小的元素。

  2. 前缀和优化：将排序后的数组计算前缀和，这样可以快速得到前k个最小元素的总和。

  3. 查找最大长度：对于每个查询值，我们需要找到最大的k，使得前k个最小元素的和不超过查询值。

具体步骤：

  • 对nums数组排序，得到从小到大的顺序
  • 计算前缀和数组，prefixSum[i]表示前i个元素的和
  • 对每个查询，使用二分查找（或线性查找）找到满足条件的最大长度

这种方法的时间复杂度主要由排序决定，为O(n log n + m log n)，其中n是nums的长度，m是queries的长度。

代码实现

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        
        // 计算前缀和
        vector<long long> prefixSum(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        vector<int> result;
        for (int query : queries) {
            // 使用二分查找找到最大长度
            int left = 0, right = nums.size();
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                if (prefixSum[mid] <= query) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            result.push_back(left);
        }
        
        return result;
    }
};

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        
        # 计算前缀和
        prefix_sum = [0]
        for num in nums:
            prefix_sum.append(prefix_sum[-1] + num)
        
        result = []
        for query in queries:
            # 使用二分查找找到最大长度
            left, right = 0, len(nums)
            while left < right:
                mid = left + (right - left + 1) // 2
                if prefix_sum[mid] <= query:
                    left = mid
                else:
                    right = mid - 1
            result.append(left)
        
        return result

public class Solution {
    public int[] AnswerQueries(int[] nums, int[] queries) {
        Array.Sort(nums);
        
        // 计算前缀和
        long[] prefixSum = new long[nums.Length + 1];
        for (int i = 0; i < nums.Length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int query = queries[i];
            // 使用二分查找找到最大长度
            int left = 0, right = nums.Length;
            while (left < right) {
                int mid = left + (right - left + 1) / 2;
                if (prefixSum[mid] <= query) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            result[i] = left;
        }
        
        return result;
    }
}

var answerQueries = function(nums, queries) {
    nums.sort((a, b) => a - b);
    
    // 计算前缀和
    const prefixSum = [0];
    for (const num of nums) {
        prefixSum.push(prefixSum[prefixSum.length - 1] + num);
    }
    
    const result = [];
    for (const query of queries) {
        // 使用二分查找找到最大长度
        let left = 0, right = nums.length;
        while (left < right) {
            const mid = left + Math.floor((right - left + 1) / 2);
            if (prefixSum[mid] <= query) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        result.push(left);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + m log n)排序需要O(n log n)，每个查询的二分查找需要O(log n)，m个查询总共O(m log n)
空间复杂度O(n)需要额外的前缀和数组存储空间

相关题目