求一列数的所有子串中,最大最小值之和小于等于给定值target的子串有多少
先sort数列,然后两个指针l和r分别从左向右、从右向左扫,如果当前range的最大最小值之和小于等于target,则l+1,可以取l以及l+1~r的每一位都可取可不取,即2^(r-l)种,否则r-1
1 #1498
2 #Runtime: 9186 ms (Beats 16.87%)
3 #Memory: 23.7 MB (Beats 81.93%)
4
5 class Solution(object):
6 def numSubseq(self, nums, target):
7 """
8 :type nums: List[int]
9 :type target: int
10 :rtype: int
11 """
12 nums.sort()
13 l, ans = 0, 0
14 r = len(nums) - 1
15 MOD = 10**9+7
16 while l <= r:
17 if nums[l] + nums[r] > target:
18 r -= 1
19 else:
20 ans += pow(2, r - l) % MOD
21 l += 1
22 return ans % MOD