[面试题] LeetCode 1546题解：和为目标值的不重叠子数组最大数目（前缀和+哈希表）

在技术招聘与团队管理中，薪资架构常是热议话题。有观点认为，个人薪资应基于其综合实力与市场价值决定，而非机械地参照团队内部现有薪酬的“平衡”。团队中因个人资历、能力、项目经验的差异，薪资水平存在差距是普遍现象。

本文将聚焦于一道考察编程与算法能力的题目，这也是技术面试中评估候选人数据结构与算法功底的重要环节。

来看下今天的算法题，这是力扣（LeetCode）上的第1546题：和为目标值且不重叠的非空子数组的最大数目，难度为中等。

题目描述

给你一个整数数组 nums 和一个整数 target。
请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target。

示例 1：

输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2。

示例 2：

输入：nums = [-1,3,5,1,4,2,-9], target = 6
输出：2
解释：总共有 3 个子数组和为 6。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6

解题思路分析

本题要求找出和为目标值 target 且互不重叠的子数组的最大数量。判断子数组和是否等于目标值，一个高效的方法是使用 前缀和 配合哈希表。这里无法使用滑动窗口，因为数组中可能包含负数，破坏了滑动窗口所需的单调性。

核心思路是：遍历数组并计算前缀和，利用哈希表记录每个前缀和首次出现的下标。当遍历到位置 i 时，当前前缀和为 preSum，我们检查 preSum - target 是否在哈希表中。如果存在，设其对应的下标为 start，那么区间 (start, i] 就是一个和为 target 的子数组。

由于子数组不能重叠，我们需要记录上一个被选中子数组的结束位置 last。只有当找到的新子数组的起始位置（开区间）大于等于 last 时，我们才选择这个子数组，并更新答案和 last 为当前子数组的结束位置（闭区间）。注意，起始位置使用开区间判断（start >= last），是因为子数组实际从 start + 1 开始。

以下是具体的代码实现。

Java 解法

public int maxNonOverlapping(int[] nums, int target) {
    int ans = 0, last = -1, preSum = 0;
    Map<Integer, Integer> mp = new HashMap<>();
    mp.put(0, -1); // 初始化，前缀和为0的下标为-1
    for (int i = 0; i < nums.length; i++) {
        preSum += nums[i];
        Integer start = mp.get(preSum - target); // 子数组起始位置（开区间）
        if (start != null && start >= last) {
            ans++;
            last = i; // 更新最后一个子数组的结束位置（闭区间）
        }
        mp.put(preSum, i); // 记录前缀和首次出现的位置
    }
    return ans;
}

C++ 解法

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int ans = 0, last = -1, preSum = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;
        for (int i = 0; i < nums.size(); i++) {
            preSum += nums[i];
            auto it = mp.find(preSum - target); // 子数组起始位置（开区间）
            if (it != mp.end() && it->second >= last) {
                ++ans;
                last = i; // 更新最后一个子数组的结束位置（闭区间）
            }
            mp[preSum] = i; // 记录前缀和首次出现的位置
        }
        return ans;
    }
};

该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，能够高效处理题目给出的数据范围。掌握此类前缀和与哈希表结合的方法是解决许多子数组求和问题的关键。