题目大意：
满足条件的子序列数目
给你一个整数数组 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^51 <= nums[i] <= 10^61 <= target <= 10^6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1498
解题思路分析：
这道题的思路是使用排序加排列组合的算法。核心逻辑是：如果当前子序列的最大值加上最小值的和小于等于target的话，那么，我们可以将该子序列分为2个部分，最小值min和其他others。那么子序列others的所有排列组合再加上min组成的序列一定符合题意。
例如：用list=[min,num1,num2,num3,num4,max]表示min+max<=target的一个子序列，这里序列长度为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)个）
解题时，我们先对数组进行排序，然后使用左右指针来确定一个区间，区间起始默认为整个数组范围。这样能够保证任何一个区间内首元素一定是区间最小值，尾元素一定是最大值。如果最小值与最大值之和大于target，我们将右指针向左移动一位。反之当前区间为一个合理区间，区间内所有包含最小值的子序列都是一个合理解，根据上文，这些合理解的个数为2^(n-1)个，n为当前区间的长度。将该个数累加至返回结果。并将左指针向右移动一位，重复执行上述逻辑，直到左指针大于右指针为止。
另外，对于java语言还有一处需要注意的地方，我们在求解幂运算时，使用Math#pow方法可能会出现long型越界，因此需要手动进行计算，即将2乘以n-1次。期间，每次相乘后将结果与1000000007求余即可解决越界问题。不过使用这种方式会导致另一个问题，由于对于每一个区间我们都要做n-1次乘法，这样效率会非常低，我们可以采用记忆数组，记录下已经计算过的幂运算结果，避免重复计算。
实现代码：
long[] memo; // 记忆数组
public int numSubseq(int[] nums, int target) {
memo = new long[nums.length]; // 初始化记忆数组
Arrays.sort(nums); // 将数组排序
int left=0,right=nums.length-1; // 左右指针
long res=0; // 返回结果
while(left<=right){ // 循环每一个区间
// 如果区间内最大值与最小值之和大于target
if(nums[left]+nums[right]>target){
right--; // 向做移动右指针
}else{ // 合理区间
// 将区间内包含min的左右排列组合数累加至返回结果
res+=pow(right-left);
// 左区间向右移动一格
left++;
}
}
return (int)(res%1000000007);
}
long pow(int time){
if(time==0) return 1;
if(memo[time]>0) return memo[time];
long res=2*pow(time-1);
res%=1000000007;
memo[time]=res;
return res;
}本题解法执行时间为33ms。
Runtime: 33 ms, faster than 100.00% of Java online submissions for Number of Subsequences That Satisfy the Given Sum Condition.
Memory Usage: 59.7 MB, less than 100.00% of Java online submissions for Number of Subsequences That Satisfy the Given Sum Condition.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1498-number-of-subsequences-that-satisfy-the-given-sum-condition-解题思路分析/