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

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

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

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

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

問題描述

來源：LeetCode第525題

難度：中等

給定一個(gè)二進(jìn)制數(shù)組 nums , 找到含有相同數(shù)量的 0 和 1 的最長連續(xù)子數(shù)組，并返回該子數(shù)組的長度。

示例1：

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

示例2：

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

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

• nums[i] 不是 0 就是 1

問題分析

這題實(shí)際上是讓求一個(gè)最長的子數(shù)組，并且這個(gè)子數(shù)組中 0 和 1 的數(shù)量必須相同。 因?yàn)閿?shù)組中的元素只能是 0 或 1 ，直接計(jì)算不太好解，我們可以換種思路， 把數(shù)組中的 0 換成 -1 。

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

我們以示例2為例來看下，改變之后的數(shù)組就變成了[-1,1,-1]。那么這題的解題思路就很明確了，我們可以直接使用前綴和，對改變之后的數(shù)組進(jìn)行累加，然后使用一個(gè)map對累加的值進(jìn)行存儲， 因?yàn)槭乔笞畲箝L度，如果遇到相同的值則不能覆蓋 。

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

累加的時(shí)候如果出現(xiàn)相同的值，只需要用當(dāng)前值的下標(biāo)減去前面相同值的下標(biāo)，中間這段就是和為0的子數(shù)組，我們只需要保存它的長度，記錄最大值即可。

這里還要注意使用map存儲前綴和的時(shí)候，要考慮 0 的情況，也就是說如果從數(shù)組的第一個(gè)元素到當(dāng)前元素nums[i]的和是 0 ，那么這個(gè)長度就是 i+1，因?yàn)閿?shù)組的下標(biāo)是從0開始的，所以這 里前綴和為 0 的時(shí)候，我們給它一個(gè)默認(rèn)值 -1 。

JAVA：

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

C++:

public:     int findMaxLength(vector

 & nums) {         unordered_map

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

筆者簡介

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