專欄：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算法文檔 。