專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一鄭州輕工業大學的學生找了一份實習的工作，HR給出了高達一千的月薪，并且在實習生考核優秀的情況下才會有，不優秀的情況下一毛錢都沒有，只報銷回去的路費。鄭州輕工業大學雖然不是什么名校，但C++開發一個月最高才能拿到1000塊錢的薪資，這也太侮辱人了。看這HR聊天的態度估計最多也只能拿個路費，并且還要干滿一個月，如果不到一個月，連路費都沒有，即便是在十多年前也沒見過這么無恥的公司，還去干啥啊。

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

來看下今天的算法題，這題是LeetCode的第525題：連續數組。

問題描述

來源：LeetCode第525題

難度：中等

給定一個二進制數組 nums , 找到含有相同數量的 0 和 1 的最長連續子數組，并返回該子數組的長度。

示例1：

輸入: nums = [0,1] 輸出: 2 說明: [0, 1] 是具有相同數量 0 和 1 的最長連續子數組。

示例2：

輸入: nums = [0,1,0] 輸出: 2 說明: [0, 1] (或 [1, 0]) 是具有相同數量0和1的最長連續子數組。

• 1 <= nums.length <= 10^5

• nums[i] 不是 0 就是 1

問題分析

這題實際上是讓求一個最長的子數組，并且這個子數組中 0 和 1 的數量必須相同。 因為數組中的元素只能是 0 或 1 ，直接計算不太好解，我們可以換種思路， 把數組中的 0 換成 -1 。

這樣 0 和 1 的數量必須相同就變成了 -1 和 1 的數量必須相同了，它們相加的結果肯定是 0 ，所以這題 就變成了求一個最長的子數組，并且這個子數組的和必須是0 。

我們以示例2為例來看下，改變之后的數組就變成了[-1,1,-1]。那么這題的解題思路就很明確了，我們可以直接使用前綴和，對改變之后的數組進行累加，然后使用一個map對累加的值進行存儲， 因為是求最大長度，如果遇到相同的值則不能覆蓋 。

關于前綴和的知識以及求最大長度，最小長度還有求頻率的總結，大家可以參考我書中 的10.3.3節，這里就不在過多介紹。

累加的時候如果出現相同的值，只需要用當前值的下標減去前面相同值的下標，中間這段就是和為0的子數組，我們只需要保存它的長度，記錄最大值即可。

這里還要注意使用map存儲前綴和的時候，要考慮 0 的情況，也就是說如果從數組的第一個元素到當前元素nums[i]的和是 0 ，那么這個長度就是 i+1，因為數組的下標是從0開始的，所以這 里前綴和為 0 的時候，我們給它一個默認值 -1 。

JAVA：

public int findMaxLength(int[] nums) {     Map
        
   map =  new HashMap<>();      map.put( 0,  -1); // 前綴和為0的時候，給一個默認值-1。      int preSum =  0, max =  0;      for ( int i =  0; i < nums.length; i++) {          // 計算前綴和，原數組中如果是0，就讓它變成-1。         preSum += nums[i] ==  0 ?  -1 :  1;          if ( map.containsKey(preSum)) {              // 如果出現相同的前綴和，就計算長度，并保存最大值。             max = Math.max(max, i -  map.get(preSum));         }  else {              // 如果沒有出現相同的前綴和，就把它存起來。              map.put(preSum, i);         }     }      return max; }

C++:

public:     int findMaxLength(vector

 & nums) {         unordered_map

  mp ;         mp[0]= -1;// 前綴和為0的時候，給一個默認值-1。         int preSum = 0, maxLength = 0;         for (int i = 0; i < nums.size(); i++) {             // 計算前綴和，原數組中如果是0，就讓它變成-1。             preSum += nums[i] == 0 ? -1 : 1;             if (mp.count(preSum)) {                 // 如果出現相同的前綴和，就計算長度，并保存最大值。                 maxLength = max(maxLength, i - mp[preSum]);             } else {                 // 如果沒有出現相同的前綴和，就把它存起來。                 mp[preSum]= i;             }         }         return maxLength;     }

筆者簡介

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