原文链接: https://leetcode-cn.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition

英文原文

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106
• 1 <= target <= 106

中文题目

给你一个整数数组 nums 和一个整数 target 。

请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

由于答案可能很大，请将结果对 10^9 + 7 取余后返回。

 

示例 1：

输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

示例 2：

输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3：

输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）

示例 4：

输入：nums = [5,2,4,1,7,6,8], target = 16
输出：127
解释：所有非空子序列都满足条件 (2^7 - 1) = 127

 

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= target <= 10^6

通过代码

高赞题解

这题一开始我打leetcode周赛的时候用的回溯算法，结果时间超了，那么表示暴力法是过不了的，所以这题需要找规律，然后用数学的方式解决。

思路：该题目只需要子数组的最小值+最大值<=target，因此，如果有个滑动窗口，滑动窗口内的最小值+最大值小于等于target的话，那么这个子数组进行排列组合，在包含最小值的情况下，排列组合的结果都符合题意。

如：用list=[min,num1,num2,num3,num4,max]表示min+max<=target的滑动窗口，这里n=len(list),n==6,包含最小值的子数组为：
[min]、[min,num1]、[min,num2]、[min,num1,num2,num3]、[min,num1,max]等等，这样的子数组有2^(n-1)个。（即[num1,num2,num3,num4,max]的全排列(2^(n-1))-1个，加上只有[min]的子数组，加起来共2^(n-1)个）

由上我们可知，我们需要首先对数组进行从小到大排序，使用双指针找到满足条件的每一对最小值和最大值，累加滑动窗口的排列组合数量就可以了。

如：经排序后的数组为[num1,num2,num3,num4,num5,num6]，output=0,双指针的索引left=0 right=5

第一步，若 num1+num5<=targer，这里num1和num5是一对最小值和最大值,output=output+2^4

第二步，双指针向内移动，left=left+1 -> num2+num5>target -> right=right-1 -> num2+num4<=target, 这里num2和num4 是一对最小值和最大值， output=output+2^2

如此迭代至 left>right 的时候，即可结束。

具体代码如下

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        if nums[0] * 2 > target:
            return 0
            
        left = 0
        right = len(nums) - 1
        res = 0
        while left <= right:
            if nums[left] + nums[right] <= target:
                res += 2**(right-left)
                left += 1
            else:
                right -= 1
        return res%(10**9+7)

8000ms居然都过了，我原来的回溯真不知道要多久。。

统计信息

通过次数	提交次数	AC比率
5439	16259	33.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言