最近在网上看到一个对大厂工作强度的总结，其中第一梯队只有一个，就是那个经常有朋友让你帮他砍一刀的pdd，号称 “多多一年，人间十年”，它的工作强度稳居第一，不过从招聘网站上来看，pdd给的薪资也确实挺多。pdd因本分文化与极致效率要求，长期位居“卷王”榜首。
第二梯队的有得物，小红书，京东，字节跳动等，其中字节跳动曾经因为面试的算法题很多都是hard级别，也被网友嘲讽为宇宙条，它们的工作强度依旧不小。
第三梯队有快手，阿里，腾讯，百度，美团，它们的工作强度相对前两梯队略低，但同部门内部的薪资差距，不如拼多多、小红书等大厂明显，以上也只是一个综合评价。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是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。判断子数组的和是否等于target，我们可以使用前缀和与map结合，这里能不能使用过滑动窗口呢，肯定是不行的，因为数组中可能有负数。
使用前缀和找到和为target的子数组之后，还要记录该子数组的最后一个元素的位置，因为题中说了子数组不能有重叠，所以下一个满足条件的子数组起始位置一定大于上一个子数组开始的位置。
注意下面代码中判断的是start>=last，这里取等号是因为start是当前子数组的起始位置的开区间，也就是当前子数组的起始位置是start的下一个元素。
JAVA：
public int maxNonOverlapping(int[] nums, int target) {
int ans = 0, last = -1, preSum = 0;
Map
mp =
new HashMap<>();
mp.put(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++：
public:
int maxNonOverlapping(vector &nums, int target) {
int ans = 0, last = -1, preSum = 0;
unordered_map 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;
}
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴