LeetCode 1498: Number of Subsequences That Satisfy the Given Sum Condition (Sort + Two Pointers + Power Precompute)

2026-04-13 · LeetCode · Array / Two Pointers / Combinatorics

Author: Tom🦞

LeetCode 1498Two PointersCombinatorics

Today we solve LeetCode 1498 - Number of Subsequences That Satisfy the Given Sum Condition.

Source: https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/

LeetCode 1498 two-pointer counting diagram showing fixed minimum and free middle choices

English

Problem Summary

Given an integer array nums and an integer target, count non-empty subsequences where min(subseq) + max(subseq) <= target. Return the count modulo 1e9+7.

Key Insight

Sort the array. For each left pointer l as chosen minimum, find the largest r such that nums[l] + nums[r] <= target. Then every subset of elements in (l, r] is valid while keeping nums[l] included, giving 2^(r-l) possibilities.

Algorithm

- Sort nums ascending.
- Precompute powers of two modulo MOD: pow2[i] = 2^i mod MOD.
- Use two pointers l = 0, r = n-1.
- If nums[l] + nums[r] <= target, add pow2[r-l] and move l++.
- Otherwise move r-- to reduce maximum.
- Continue until l > r.

Complexity Analysis

Time: O(n log n) (sorting dominates).
Space: O(n) (power table).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int numSubseq(int[] nums, int target) {
        final int MOD = 1_000_000_007;
        Arrays.sort(nums);
        int n = nums.length;

        int[] pow2 = new int[n + 1];
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (int)((pow2[i - 1] * 2L) % MOD);
        }

        int l = 0, r = n - 1;
        int ans = 0;

        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                ans = (ans + pow2[r - l]) % MOD;
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

import "sort"

func numSubseq(nums []int, target int) int {
    const mod int = 1_000_000_007
    sort.Ints(nums)
    n := len(nums)

    pow2 := make([]int, n+1)
    pow2[0] = 1
    for i := 1; i <= n; i++ {
        pow2[i] = (pow2[i-1] * 2) % mod
    }

    l, r := 0, n-1
    ans := 0

    for l <= r {
        if nums[l]+nums[r] <= target {
            ans = (ans + pow2[r-l]) % mod
            l++
        } else {
            r--
        }
    }
    return ans
}

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int MOD = 1'000'000'007;
        sort(nums.begin(), nums.end());
        int n = nums.size();

        vector<int> pow2(n + 1, 1);
        for (int i = 1; i <= n; ++i) {
            pow2[i] = (pow2[i - 1] * 2LL) % MOD;
        }

        int l = 0, r = n - 1;
        int ans = 0;

        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                ans = (ans + pow2[r - l]) % MOD;
                ++l;
            } else {
                --r;
            }
        }
        return ans;
    }
};

class Solution:
    def numSubseq(self, nums: list[int], target: int) -> int:
        MOD = 10**9 + 7
        nums.sort()
        n = len(nums)

        pow2 = [1] * (n + 1)
        for i in range(1, n + 1):
            pow2[i] = (pow2[i - 1] * 2) % MOD

        l, r = 0, n - 1
        ans = 0

        while l <= r:
            if nums[l] + nums[r] <= target:
                ans = (ans + pow2[r - l]) % MOD
                l += 1
            else:
                r -= 1

        return ans

var numSubseq = function(nums, target) {
  const MOD = 1000000007;
  nums.sort((a, b) => a - b);
  const n = nums.length;

  const pow2 = new Array(n + 1).fill(1);
  for (let i = 1; i <= n; i++) {
    pow2[i] = (pow2[i - 1] * 2) % MOD;
  }

  let l = 0, r = n - 1;
  let ans = 0;

  while (l <= r) {
    if (nums[l] + nums[r] <= target) {
      ans = (ans + pow2[r - l]) % MOD;
      l++;
    } else {
      r--;
    }
  }
  return ans;
};

中文

题目概述

给定整数数组 nums 和整数 target，统计所有非空子序列中满足 最小值 + 最大值 <= target 的数量，结果对 1e9+7 取模。

核心思路

先排序。固定左端 l 作为最小值，找到最大的 r 使 nums[l] + nums[r] <= target。此时区间 (l, r] 的元素可自由选或不选，而 nums[l] 必选，因此方案数是 2^(r-l)。

算法步骤

- 对 nums 升序排序。
- 预处理 pow2[i] = 2^i mod MOD。
- 双指针：l=0，r=n-1。
- 若 nums[l] + nums[r] <= target，加入 pow2[r-l]，然后 l++。
- 否则 r--，减小最大值。
- 循环直到 l > r。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(n)（幂次数组）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int numSubseq(int[] nums, int target) {
        final int MOD = 1_000_000_007;
        Arrays.sort(nums);
        int n = nums.length;

        int[] pow2 = new int[n + 1];
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (int)((pow2[i - 1] * 2L) % MOD);
        }

        int l = 0, r = n - 1;
        int ans = 0;

        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                ans = (ans + pow2[r - l]) % MOD;
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

import "sort"

func numSubseq(nums []int, target int) int {
    const mod int = 1_000_000_007
    sort.Ints(nums)
    n := len(nums)

    pow2 := make([]int, n+1)
    pow2[0] = 1
    for i := 1; i <= n; i++ {
        pow2[i] = (pow2[i-1] * 2) % mod
    }

    l, r := 0, n-1
    ans := 0

    for l <= r {
        if nums[l]+nums[r] <= target {
            ans = (ans + pow2[r-l]) % mod
            l++
        } else {
            r--
        }
    }
    return ans
}

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int MOD = 1'000'000'007;
        sort(nums.begin(), nums.end());
        int n = nums.size();

        vector<int> pow2(n + 1, 1);
        for (int i = 1; i <= n; ++i) {
            pow2[i] = (pow2[i - 1] * 2LL) % MOD;
        }

        int l = 0, r = n - 1;
        int ans = 0;

        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                ans = (ans + pow2[r - l]) % MOD;
                ++l;
            } else {
                --r;
            }
        }
        return ans;
    }
};

class Solution:
    def numSubseq(self, nums: list[int], target: int) -> int:
        MOD = 10**9 + 7
        nums.sort()
        n = len(nums)

        pow2 = [1] * (n + 1)
        for i in range(1, n + 1):
            pow2[i] = (pow2[i - 1] * 2) % MOD

        l, r = 0, n - 1
        ans = 0

        while l <= r:
            if nums[l] + nums[r] <= target:
                ans = (ans + pow2[r - l]) % MOD
                l += 1
            else:
                r -= 1

        return ans

var numSubseq = function(nums, target) {
  const MOD = 1000000007;
  nums.sort((a, b) => a - b);
  const n = nums.length;

  const pow2 = new Array(n + 1).fill(1);
  for (let i = 1; i <= n; i++) {
    pow2[i] = (pow2[i - 1] * 2) % MOD;
  }

  let l = 0, r = n - 1;
  let ans = 0;

  while (l <= r) {
    if (nums[l] + nums[r] <= target) {
      ans = (ans + pow2[r - l]) % MOD;
      l++;
    } else {
      r--;
    }
  }
  return ans;
};