当前位置: 萬仟网 > IT编程>开发语言>.net > LeetCode1498. 满足条件的子序列数目

LeetCode1498. 满足条件的子序列数目

2020年07月07日  | 萬仟网IT编程  | 我要评论
题目给你一个整数数组 nums 和一个整数 target 。请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的非空子序列的数目。由于答案可能很大,请将结果对 10^9 + 7 取余后返回。思路排序 + 双指针将数组从小到大排序, 双指针left指向排好序的第一个元素, right指向最后一个.首先寻找符合条件的左右端点, 显然nums[left] + nums[right] <= target 时,符合条件, 此时我们统计可以使用的子序列个数为2r

题目

给你一个整数数组 nums 和一个整数 target

请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target非空子序列的数目。

由于答案可能很大,请将结果对 10^9 + 7 取余后返回。

思路

排序 + 双指针

将数组从小到大排序, 双指针left指向排好序的第一个元素, right指向最后一个.

首先寻找符合条件的左右端点, 显然nums[left] + nums[right] <= target 时,符合条件, 此时我们统计可以使用的子序列个数为2rl2^{r -l}, 注意每次都默认使用左指针指向的元素. 统计后移动左指针. 这样, 每一次循环子序列不会发生漏记的情况(子序列最小值都是没有使用过的最小值).

代码如下

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        if nums[0] * 2 > target:
            return 0
        MOD = 10 ** 9 + 7
        left = 0
        right = len(nums) - 1
        ret = 0
        while left <= right:
            if nums[left] + nums[right] <= target:
                ret += 2**(right-left)
                ret %= MOD
                left += 1
            else:
                right -= 1
        return ret

本文地址:https://blog.csdn.net/Hoooo_233/article/details/107140413

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。

相关文章:

验证码:
Copyright © 2017-2021  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com