本文主要是介绍leetcode:1498,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题
满足所给数字和的数字子串:
- 给你一个整数数组 nums 和一个整数 target 。
- 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
- 由于答案可能很大,请将结果对 10^9 + 7 取余后返回。
思路
- 首先肯定对原数组进行排序
- 当排序后数组的一个子数组 n u m s [ l e f t : r i g h t ] nums[left:right] nums[left:right] 存在 n u m s [ l e f t ] + n u m s [ r i g h t ] < t a r g e t nums[left]+nums[right]<target nums[left]+nums[right]<target , 那么这个数组下的,所有包含 n u m s [ l e f t ] nums[left] nums[left] 的子数组都满足条件,总个数为:
r e s + = 2 r i g h t − l e f t − 1 res+=2^{right-left-1} res+=2right−left−1 - left 从 0 开始,right 从len-1 开始
- 当 n u m s [ l e f t ] + n u m s [ r i g h t ] < = t a r g e t nums[left]+nums[right]<=target nums[left]+nums[right]<=target 时,更新 res。
- 此时以left为起点的所有满足子数组已经算完,因此:
l e f t + + left++ left++
- 此时以left为起点的所有满足子数组已经算完,因此:
- 当 n u m s [ l e f t ] + n u m s [ r i g h t ] > t a r g e t nums[left]+nums[right]>target nums[left]+nums[right]>target 时,
- 当前数组中,可能包含存在left的符合条件的子数组(只需要加一个不那么大的数即可)
- 当前数组中,绝不会存在包含right的符合条件的子数组,因为left已经是最小的了,right没法再加一个更小的。因此,
r i g h t − − right-- right−−
class Solution(object):def numSubseq(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""x = 1000000007max_len = 1000000powarr=[1]for _ in range(1,max_len):powarr.append((powarr[-1]*2%x)) nums = sorted(nums)# print(nums)left = 0right = len(nums)-1res = 0while(left<=right):if nums[left]+nums[right]<=target:res=(res+ powarr[right-left])%x# print(left,right,res)left+=1else:right-=1return res
这篇关于leetcode:1498的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!