求包含和为k的子序列的最短子数组长度——优化算法问询

首先明确核心前提：题目中所有元素都是正整数，这是我们能大幅优化时间复杂度的关键依据。

先澄清概念：子数组 vs 子序列 #

你给出的示例提到最短长度为5，但按子序列（元素不连续）计算能找到更短的组合（比如61+28+11=100，长度3），这说明你可能混淆了两者定义：

• 子数组：元素必须连续
• 子序列：元素可以不连续

下面针对两种场景分别给出优化解法：

场景1：寻找和≥k的连续子数组（匹配你的示例） #

因为元素全为正，滑动窗口（双指针）是最优解法，时间复杂度O(n)，空间复杂度O(1)，远优于原O(n²k)的三层循环。

思路 #

用左右两个指针维护滑动窗口：

1. 右指针不断右移，累加窗口内元素和，直到和≥k
2. 当窗口和满足条件时，尝试左移左指针缩小窗口，同时更新最短长度，直到窗口和小于k
3. 遍历结束后，若找到有效长度则返回，否则返回-1

Java代码示例 #

import java.util.Arrays;

public class ShortestSubarraySolver {
    public static int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLen = Integer.MAX_VALUE;
        int currentSum = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            currentSum += nums[right];

            // 当和≥k时，尝试缩小窗口以找到更短长度
            while (currentSum >= k) {
                minLen = Math.min(minLen, right - left + 1);
                currentSum -= nums[left];
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }

    public static void main(String[] args) {
        int[] nums = {12,42,11,2,28,6,61,88};
        int k = 100;
        System.out.println(shortestSubarray(nums, k)); // 输出5，匹配示例
    }
}

场景2：寻找和为k的子序列（元素不连续） #

我们可以用动态规划将时间复杂度降到O(nk)，相比原O(n²k)的效率提升几个数量级。

思路 #

定义dp[j]表示和为j的最短子序列长度：

1. 初始化dp[0] = 0（和为0不需要任何元素），其余dp[j]设为n+1（表示初始无法达到该和）
2. 遍历每个数字num，从k到num倒序更新dp数组：dp[j] = Math.min(dp[j], dp[j - num] + 1)（倒序遍历避免重复使用当前数字，若允许重复使用则正序遍历）
3. 遍历结束后，若dp[k] ≤ n则返回该长度，否则返回-1

Java代码示例 #

import java.util.Arrays;

public class ShortestSubsequenceSolver {
    public static int shortestSubsequence(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[k + 1];
        Arrays.fill(dp, n + 1);
        dp[0] = 0;

        for (int num : nums) {
            for (int j = k; j >= num; j--) {
                dp[j] = Math.min(dp[j], dp[j - num] + 1);
            }
        }

        return dp[k] <= n ? dp[k] : -1;
    }

    public static void main(String[] args) {
        int[] nums = {12,42,11,2,28,6,61,88};
        int k = 100;
        System.out.println(shortestSubsequence(nums, k)); // 输出3
    }
}

复杂度分析 #

• 时间复杂度：O(nk)，n和k均不超过3000，总操作数约900万，完全在可接受范围内
• 空间复杂度：O(k)，仅需一个大小为k+1的数组

内容的提问来源于stack exchange，提问作者CodeCrusader