給出一列數(shù)nums[i]以及一些query q[j]，輸出ans[j]表示從nums[i]中可以最多選擇幾個(gè)數(shù)使得加和不超過q[j]。
仔細(xì)想想就發(fā)現(xiàn)雖然題目中說nums順序不可交換，但因?yàn)榭梢噪S意取一些跳過一些，所以其實(shí)順序并不影響，所以先對nums排序，然后預(yù)處理prefix sum，之后對于每個(gè)查詢q[j]，二分prefix sum，看最多可以取多少個(gè)數(shù)，用python自帶的二分函數(shù)依舊更快一些
用python自帶函數(shù)
1 #2389
2 #Runtime: 86 ms (Beats 97.67%)
3 #Memory: 13.9 MB (Beats 29.7%)
4
5 class Solution(object):
6 def answerQueries(self, nums, queries):
7 """
8 :type nums: List[int]
9 :type queries: List[int]
10 :rtype: List[int]
11 """
12 nums.sort()
13 sums = [nums[0]]
14 for i in range(1, len(nums)):
15 sums.append(sums[-1] + nums[i])
16 ans = []
17 for q in queries:
18 ans.append(bisect_right(sums, q))
19 return ans
手寫二分：
1 #2389
2 #Runtime: 93 ms (Beats 95.35%)
3 #Memory: 13.8 MB (Beats 56.98%)
4
5 class Solution(object):
6 def answerQueries(self, nums, queries):
7 """
8 :type nums: List[int]
9 :type queries: List[int]
10 :rtype: List[int]
11 """
12 nums.sort()
13 sums = [nums[0]]
14 for i in range(1, len(nums)):
15 sums.append(sums[-1] + nums[i])
16 ans = []
17 for q in queries:
18 l = 0
19 r = len(nums)
20 while l < r:
21 mid = (l + r) // 2
22 if sums[mid] > q:
23 r = mid
24 else:
25 l = mid + 1
26 ans.append(l)
27 return ans