專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

一hr在網(wǎng)上發(fā)文稱：面試了一個985碩士，技術(shù)面試通過了，業(yè)務(wù)面試官評價項目經(jīng)驗也有，開發(fā)能力也不錯，但還是不錄用他！因為他期望薪資是28k，25k也可以接受，而公司最多只能給到25k。錄用的話還得跟領(lǐng)導(dǎo)審批，業(yè)務(wù)面試官也覺得給太高不利于目前團隊薪資平衡。

給高了不利于團隊薪資平衡？哪家公司能做到薪資平衡，一個團隊中薪資高低很正常，有的相差兩三倍都有可能，因為每個人的學(xué)歷不同，工作年薪不同，能力不同，薪資有差別是很正常的。

個人的工資水平是根據(jù)個人的綜合實力來決定的，而不是根節(jié)團隊的平均薪資來決定的。

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

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

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

示例1：

輸入：nums = [1,1,1,1,1], target = 2 輸出：2 解釋：總共有 2 個不重疊子數(shù)組（加粗?jǐn)?shù)字表示） [1,1,1,1,1] ，它們的和為目標(biāo)值 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結(jié)合，這里能不能使用過滑動窗口呢，肯定是不行的，因為數(shù)組中可能有負(fù)數(shù)。

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

注意下面代碼中判斷的是start>=last，這里取等號是因為start是當(dāng)前子數(shù)組的起始位置的開區(qū)間，也就是當(dāng)前子數(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ū)間的結(jié)束位置，閉區(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ū)間的結(jié)束位置，閉區(qū)間             }             mp[preSum] = i;         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。