室友面试作弊被我举报了。。。

最近一网友在网上发文称：自己和室友在同一家公司面试，结果室友过了，他没过，本来也无所谓，结果室友在他面前炫耀，说自己面试用ai工具作弊了，面试官没发现。他一怒之下跟hr举报了，结果他室友的offer被取消了。

只能说该室友还是太年前，作弊面试过了也不是什么光荣的事，没什么值得炫耀的，即便是靠自己真本事面试通过，也要学会低调。要做到不露圭角，韬光养晦。并且该网友估计也不是啥好人，对于这种喜欢举报的人也要尽量远离。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是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多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。