2389. 和有限的最长子序列

Posted on | In | |

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-subsequence-with-limited-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题拿过来第一眼就觉得nums可以排序，然后又仔细看了看题目说不能影响顺序，就放弃了排序的想法，经过评论区提醒才发现，加法条件，排序不排序对元素顺序哪有什么影响。。又是被忽悠的一天。。。
可以排序就省事很多了，首先想到的就是循环解决，然后觉得递归也能解决，然后还觉得quries那里应该也可以做一些手脚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def answerQueries(self, nums, queries):
        """
        :type nums: List[int]
        :type queries: List[int]
        :rtype: List[int]
        """
        nums.sort()
        answer = list()
        for i in range(len(queries)):
            res = 0
            count = 0
            for item in nums:
                res += item
                if res <= queries[i]:
                    count += 1
                # else:
            answer.append(count) 
        return answer

然后想办法写成递归，好像写不成递归啊，递归的出口是已知的，这里是未知的，所以应该写不成递归？？quries想了想好像也没什么动手脚的余地，折腾来折腾去每次遍历的次数也不会改变。
然后在官解中看到了“前缀和”的概念。