Open yankewei opened 2 years ago
从题目中分析出几个条件:
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
}
给你一个长度为
n
的整数数组nums
,和一个长度为m
的整数数组queries
。返回一个长度为
m
的数组answer
,其中answer[i]
是nums
中元素之和小于等于queries[i]
的子序列的最大长度 。子序列是由一个数组删除某些元素(也可以不删除)但不改变剩余元素顺序得到的一个数组。
示例 1:
示例 2:
提示:
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/longest-subsequence-with-limited-sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。