“方生方死，方死方生。”——《庄子》

题目

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

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

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

难度：中等

分析

笔者受滑动数组的影响，一直想着固定右边界，故而没做出来，其实固定左边界就行了💤。

由于此题求的是子序列的数组，与顺序无关，需要判断最小元素与最大元素，因此先对数组进行排序。我们遍历数组，把当前的值nums[i]作为子序列的左边界（必须取该值，不然会重复），则右边界的值需满足nums[j]<=target-nums[i]。因为数组已排序，我们使用二分查找找到最后一个满足条件的下标j，不能取[j+1,]区间的值，否则会破坏条件，而[i+1,j]区间的值可取可不取，所以对于左边界nums[i]，一共有种子序列。该幂运算结果可能非常大，故使用快速幂，将结果累加取余得到最终答案。

解答

class Solution {public int numSubseq(int[] nums, int target) {long ans=0;Arrays.sort(nums);for (int i=0;i<nums.length&&nums[i]*2<=target;i++){int pos=binarySearch(nums,target-nums[i])-1;long add=(pos>=i)?pow(2,pos-i,1000000007):0;ans=(ans+add)%1000000007;}return (int)ans;}private long pow(long x, long y, long MOD){long ans=1;while (y>0){if ((y&1)==1){ans=(ans*x)%MOD;}y>>=1;x=(x*x)%MOD;}return ans;}private int binarySearch(int[] nums, int target) {int low = 0, high = nums.length;while (low < high) {int mid = (high - low) / 2 + low;if (mid == nums.length) {return mid;}int num = nums[mid];if (num <= target) {low = mid + 1;} else {high = mid;}}return low;}
}

“有学问的傻瓜，要远比无知的傻瓜还要愚蠢。”——伏尔泰