子数组和最接近目标值的解法详解

1. 概述

在数组处理中，寻找满足特定条件的子数组是一个经典问题。本文重点讨论一个具体场景：在不超出目标值的前提下，找到和最接近目标值的子数组。

我们将介绍三种解决方案，并分析它们的适用场景和时间复杂度，帮助你在实际开发中快速选择最优解法。

---

2. 问题定义

给定一个数组 A 和一个目标值 k，我们需要找到一个子数组，其元素之和不超过 k，并且尽可能接近 k。

举个例子：

数组 A = [1, 2, 3, 4, 5, 6, 7]
目标值 k = 12

我们希望找到一个子数组，比如 [2, 3, 4, 2]，它们的和为 11，是最接近 12 且不超过它的子数组。

---

3. 暴力解法（Brute Force）

✅ 思路

遍历所有可能的子数组，计算它们的和，保留最接近 k 且不超过 k 的最大值。

❌ 缺点

• 时间复杂度为 **O(n²)**，对于大数组效率低下。
• 只适用于非负数数组（否则会出现“先超限后变小”的情况）。

✅ 示例代码

int maxSubarraySum(int[] A, int k) {
    int n = A.length;
    int answer = 0;
    for (int L = 0; L < n; L++) {
        int sum = 0;
        int R = L;
        while (R < n && sum + A[R] <= k) {
            sum += A[R];
            R++;
        }
        answer = Math.max(answer, sum);
    }
    return answer;
}

---

4. 双指针解法（Two-Pointers）

✅ 思路

利用滑动窗口思想，避免重复计算子数组和，提升效率。

• 使用两个指针 L 和 R，分别表示子数组的起始和结束位置。
• 每次移动 L 时，仅减去前一个元素的值，继续从当前 R 位置向右扩展。

⚠️ 注意

• 仍然仅适用于非负数数组。
• 时间复杂度优化到 **O(n)**。

✅ 示例代码

int maxSubarraySum(int[] A, int k) {
    int n = A.length;
    int answer = 0, sum = 0, R = 0;
    for (int L = 0; L < n; L++) {
        if (L > 0) sum -= A[L - 1];
        while (R < n && sum + A[R] <= k) {
            sum += A[R];
            R++;
        }
        answer = Math.max(answer, sum);
    }
    return answer;
}

---

5. 前缀和解法（Prefix Sum）

✅ 思路

适用于包含负数的数组。使用前缀和数组和 TreeSet（或类似结构）进行查找：

• 构建前缀和数组 prefix，其中 prefix[i] 表示前 i 个元素的和。
• 对于每个 i，我们希望找到一个 j < i，使得 prefix[i] - prefix[j] <= k 且尽可能接近 k。
• 即，我们要找最大的 prefix[j]，使得 prefix[j] >= prefix[i] - k。

✅ 数据结构

• 使用 TreeSet 来维护已出现的 prefix[j]，并支持快速查找。

⚠️ 时间复杂度

• **O(n log n)**，适用于包含负数的数组。

✅ 示例代码

import java.util.TreeSet;

int maxSubarraySum(int[] A, int k) {
    int n = A.length;
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + A[i];
    }

    int answer = 0;
    TreeSet<Integer> set = new TreeSet<>();
    set.add(prefix[0]);

    for (int i = 1; i <= n; i++) {
        Integer target = set.floor(prefix[i] - k);
        if (target != null) {
            answer = Math.max(answer, prefix[i] - target);
        }
        set.add(prefix[i]);
    }
    return answer;
}

---

6. 方法对比

方法	适用条件	时间复杂度	是否支持负数	总体评价
暴力解法	非负数	O(n²)	❌	不推荐
双指针解法	非负数	O(n)	❌	快速有效
前缀和解法	任意数	O(n log n)	✅	通用性强

---

7. 总结

三种方法各有优劣：

• 如果数组中不含负数，优先使用 双指针解法，效率最高。
• 如果数组中可能包含负数，必须使用 前缀和 + TreeSet 的方式。
• 暴力解法虽然直观，但性能差，只适合小规模数据或作为验证手段。

在实际开发中，建议根据数据特性选择合适算法，避免踩坑。