import java.util.Arrays; class Solution { public int numSubseq(int[] nums, int target) { Arrays.sort(nums); int len = nums.length; long ans = 0l; for (int i = 0; i < len; i++) { if( nums[i]*2 <= target){ int idx = upperBound(nums,0,len,target-nums[i]); int rightmost = idx - 1; ans = ans + pow(rightmost-i); ans %= 1000000007; } } return (int)ans; } public long pow(int x){ if( x == 0){ return 1; } if( x == 1){ return 2; } long y = pow(x/2); if( x % 2 == 1){ return y*y*2%1000000007; } return y*y%1000000007; } /** * 返回大于key的第一个 * * @param arr * @param start * @param high * @param key * @return */ public int upperBound(int[] arr, int start, int high, int key) { while (start < high) { int mid = (start+high)/2; if(arr[mid] >key){ high = mid; }else{ start = mid+1; } } return high; } }