最近一網(wǎng)友在網(wǎng)上發(fā)文稱：自己和室友在同一家公司面試，結果室友過了，他沒過，本來也無所謂，結果室友在他面前炫耀，說自己面試用ai工具作弊了，面試官沒發(fā)現(xiàn)。他一怒之下跟hr舉報了，結果他室友的offer被取消了。

只能說該室友還是太年前，作弊面試過了也不是什么光榮的事，沒什么值得炫耀的，即便是靠自己真本事面試通過，也要學會低調(diào)。要做到不露圭角，韜光養(yǎng)晦。并且該網(wǎng)友估計也不是啥好人，對于這種喜歡舉報的人也要盡量遠離。

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

來看下今天的算法題，這題是LeetCode的第1546題：和為目標值且不重疊的非空子數(shù)組的最大數(shù)目，難度是中等。

給你一個數(shù)組 nums 和一個整數(shù) target 。請你返回 非空不重疊子數(shù)組的最大數(shù)目，且每個子數(shù)組中數(shù)字和都為 target 。

示例1：

輸入：nums = [1,1,1,1,1], target = 2 輸出：2 解釋：總共有 2 個不重疊子數(shù)組（加粗數(shù)字表示） [1,1,1,1,1] ，它們的和為目標值 2 。

示例2：

輸入：nums = [-1,3,5,1,4,2,-9], target = 6 輸出：2 解釋：總共有 3 個子數(shù)組和為 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

問題分析

這題讓找出最多的子數(shù)組個數(shù)，并且每個子數(shù)組的和等于target。判斷子數(shù)組的和是否等于target，我們可以使用前綴和與map結合，這里能不能使用過滑動窗口呢，肯定是不行的，因為數(shù)組中可能有負數(shù)。

使用前綴和找到和為target的子數(shù)組之后，還要記錄該子數(shù)組的最后一個元素的位置，因為題中說了子數(shù)組不能有重疊，所以下一個滿足條件的子數(shù)組起始位置一定大于上一個子數(shù)組開始的位置。

注意下面代碼中判斷的是start>=last，這里取等號是因為start是當前子數(shù)組的起始位置的開區(qū)間，也就是當前子數(shù)組的起始位置是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);// 區(qū)間的起始位置，開區(qū)間         if (start != null && start >= last) {             ans++;             last = i;// 區(qū)間的結束位置，閉區(qū)間         }         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);// 區(qū)間的起始位置，開區(qū)間             if (it != mp.end() && it->second >= last) {                 ++ans;                 last = i;// 區(qū)間的結束位置，閉區(qū)間             }             mp[preSum] = i;         }         return ans;     }
             
           

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結構和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解900多題，對算法題有自己獨特的解題思路和解題技巧。