two pointer O(nlogn) time O(n) space
这道题找的是subsequence不是subarray！！！
举例nums = [5,2,4,1,7,6,8], target = 11
对于1来说因为最大的数是8使得两数之和小于target11 所以除了自身必须要在subsequence里 其他任何数（包括8）都可在可不在所选的subsequence里 所以这样的subsequence共有26个
对于5来说 除了7和8不能选 其他不小于5的数都可选 这样的数只有6一个 所以这样的subsequence共有2个
所以这道题的答案跟每个数的原始位置没有任何关系！！！直接排序即可！！！然后按照two sum去做
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
sort(begin(nums), end(nums));
int l = 0, n = nums.size(), r = n - 1, M = 1e9 + 7, res = 0;
vector<int> pow2(n, 1);
for (int i = 1; i < n; ++i) {
pow2[i] = (pow2[i - 1] * 2) % M;
}
while (l <= r) {
if (nums[l] + nums[r] <= target) {
res = (res + pow2[r - l++]) % M;
} else {
--r;
}
}
return res;
}
};
|