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

題目

給你一個整數數組?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;}
}

“有學問的傻瓜，要遠比無知的傻瓜還要愚蠢。”——伏爾泰