和有限的最长子序列

[yankewei]

给你一个长度为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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-subsequence-with-limited-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[yankewei]

从题目中分析出几个条件：

• 没有要求返回子序列，所以不用关注顺序
• 题目中要求找到最大长度的子序列，所以我们可以先求的数组的和，尽可能的保证长度最长就要舍掉值最大的数

暴力模拟

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer[] $queries
     * @return Integer[]
     */
    function answerQueries($nums, $queries) {
        $answer = [];
        sort($nums);
        $sum = array_sum($nums);
        foreach ($queries as $query) {
            $dump = $nums;
            $in_sum = $sum;

            while (count($dump) >= 0) {
                if ($in_sum > $query) {
                    $in_sum -= array_pop($dump);
                } else {
                    $answer[] = count($dump);
                    break;
                }
            }
            
        }
        
        return $answer;
    }
}

前缀和

排序之后再前缀和，得出的结果就是一个有序数组的前缀和，可以直接反应出小于某一个值的最大长度，完美解决, 由于懒得写二分查找，所以就用Go自带的二分查找算法

func answerQueries(nums []int, queries []int) []int {
    sort.Ints(nums)
    pre_sum := make([]int, len(nums))
    pre_sum[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        pre_sum[i] = nums[i] + pre_sum[i-1]
    }
    fmt.Println(pre_sum)
    ans := make([]int, len(queries))

    for i := 0; i < len(queries); i++ {
        ans[i] = sort.SearchInts(pre_sum, queries[i]+1)
    }

    return ans
}