LeetCode 1498. 满足条件的子序列数目

Categories:

题目描述
思路分析
1. 解法一：排序 + 双指针 + 快速幂（推荐）
相似题目

题目描述

✅ 1498. 满足条件的子序列数目

思路分析

解法一：排序 + 双指针 + 快速幂（推荐）

核心思路：

排序后子序列的最小值和最大值分别由左端点和右端点决定，与元素选取方式无关

固定左指针 left（子序列最小值），用二分或右指针找到最大的 right 使得 nums[left] + nums[right] <= target

在 [left+1, right] 范围内的元素可以任意选取或不选，共 2^(right-left) 种合法子序列

预先计算 2 的幂次（取模）避免重复计算

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数组长度，排序 O(n log n)，双指针 O(n)

空间复杂度：O(n)，预存幂次数组

class Solution {
    private static final int MOD = 1_000_000_007;

    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);

        int n = nums.length;

        // 预计算 2 的幂次（取模）
        long[] pow = new long[n];
        pow[0] = 1;
        for (int i = 1; i < n; i++) {
            pow[i] = pow[i - 1] * 2 % MOD;
        }

        long ans = 0;
        int left = 0;
        int right = n - 1;

        // 双指针统计合法子序列数
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                // [left+1, right] 内元素任意选取，共 2^(right-left) 个子序列
                ans = (ans + pow[right - left]) % MOD;
                left++;
            } else {
                right--;
            }
        }

        return (int) ans;
    }
}

func numSubseq(nums []int, target int) int {
    const mod = 1_000_000_007

    sort.Ints(nums)
    n := len(nums)

    // 预计算 2 的幂次（取模）
    pow := make([]int, n)
    pow[0] = 1
    for i := 1; i < n; i++ {
        pow[i] = pow[i-1] * 2 % mod
    }

    ans := 0
    left, right := 0, n-1

    // 双指针统计合法子序列数
    for left <= right {
        if nums[left]+nums[right] <= target {
            // [left+1, right] 内元素任意选取，共 2^(right-left) 个子序列
            ans = (ans + pow[right-left]) % mod
            left++
        } else {
            right--
        }
    }

    return ans
}

相似题目

题目	难度	考察点
1099. 小于 K 的两数之和	简单	排序、双指针
15. 三数之和	中等	排序、双指针
16. 最接近的三数之和	中等	排序、双指针
923. 三数之和的多种可能	中等	双指针、计数
2561. 重排水果	困难	排序、双指针
1877. 数组中最大数对和的最小值	中等	排序、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2020/93670217