专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一hr在网上发文称：面试了一个985硕士，技术面试通过了，业务面试官评价项目经验也有，开发能力也不错，但还是不录用他！因为他期望薪资是28k，25k也可以接受，而公司最多只能给到25k。录用的话还得跟领导审批，业务面试官也觉得给太高不利于目前团队薪资平衡。
给高了不利于团队薪资平衡？哪家公司能做到薪资平衡，一个团队中薪资高低很正常，有的相差两三倍都有可能，因为每个人的学历不同，工作年薪不同，能力不同，薪资有差别是很正常的。
个人的工资水平是根据个人的综合实力来决定的，而不是根节团队的平均薪资来决定的。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是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算法文档 。
热门跟贴