[LeetCode]1498. Number of Subsequences That Satisfy the Given Sum Condition (Medium) Python-2023.05.06
Posted on 2023-05-06 17:28 Uriel 閱讀(52) 評論(0) 編輯 收藏 引用 所屬分類: 閑來無事重切Leet Code 、游標.移動窗口 、排序求一列數的所有子串中,最大最小值之和小于等于給定值target的子串有多少
先sort數列,然后兩個指針l和r分別從左向右、從右向左掃,如果當前range的最大最小值之和小于等于target,則l+1,可以取l以及l+1~r的每一位都可取可不取,即2^(r-l)種,否則r-1
先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
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