文章目錄
-
-
-
- 了解題意
- 思考過程
- 求數組中和等于給定值的最長子數組
- 代碼實作
- 總結
-
-
前幾天公司社招面了幾個同學，和其它面試官交流後聽到了其中一個同僚常用的一個算法題，這道算法題幾乎決定了能否通過該面試官，題目比較有意思，是這樣的，給定一個數組，求出奇數和偶數個數相同的最長連續子數組，有的同學可能聽過這個題目，沒有聽過的同學可以先自己想想該怎麼解決這個問題。
了解題意
這是什麼意思呢，假設給定數組[2,2,2,3,4,5,6,7,7,7]，那麼奇數和偶數個數相同的最長連續子數組是[2,2,3,4,5,6,7,7]，這個數組中奇數和個數和偶數的個數相等都是4個。再假設給定數組[1,2,3,4,5,6]，那麼奇數和偶數個數相同的最長連續子數組是其本身，整個數組奇數和偶數的個數相等是3個，現在你應該明白題目的意思了吧。
思考過程
這個題目我還是第一次聽到，是以開始想如果我在面試時遇到這個題目該如何求解呢？我的第一反應是記錄奇數和偶數個數是比較繁瑣的過程，能不能把問題轉化一下呢？
反正是計算奇數或者偶數的個數，那麼幹脆就先對數組處理一下，把奇數修改為1，把偶數修改為0，那麼對于數組[2,2,2,3,4,5,6,7,7,7]經過上述轉換後就變為了[0,0,0,1,0,1,0,1,0,1,1,1]，然後我們來看看問題是不是變的簡單了一些。
實際上有的同學可能已經看出來了，把奇數修改為1，把偶數修改為0并沒有簡化問題，我們依然需要計算1的個數和0的個數，這樣的轉換沒有達到簡化問題的目的。
還有沒有更好的轉換方法嗎，奇數的個數和偶數的個數相同可以等價轉換為什麼呢？大家可以先自己想一想這個問題。
也許有的同學已經想出來了，上述過程中既然把奇數修改為了1，那麼我們可以把偶數修改為-1，這樣奇數的個數和偶數的個數相同就等價轉換為了這個子數組的和為0，這樣的轉換極大的簡化了問題的求解過程。
是以我們可以看到問題等價轉換的思維方式在求解算法這類問題時是非常有用的。
現在我們知道了這個問題可以轉換為求“和為0的最長連續子數組”，在這裡需要意識到和為0是一個非常具體的問題，有時候求解這類具體的問題可能沒有求解通用的問題來的簡單，那麼什麼是通用的問題呢？也就是說我們不去求解“和為0的最長連續子數組”，而是試圖求解“和為給定值的最長連續子數組”。
求數組中和等于給定值的最長子數組
現在我們已經将最初的求奇數和偶數個數相同的最長連續子數組轉換為了求和等于給定值的最長子數組，那麼這個新的問題該如何解決呢？
我們首先來想最簡單的解法，隻要找出所有的子數組，然後計算出每個子數組的和并判斷是否等于給定值，如果等于給定值并且其長度大于之前的記錄那麼更新記錄，這種解法非常簡單，但是時間複雜度也很高，為O(n^3)，有沒有更好的解決嗎？答案是肯定的。
實際上對于最後求解的子數組必然是以某個元素為結尾的，是以對于數組中的每個元素我們去計算以該元素為結尾的子數組是否其和等于給定值，這句話非常重要，是解決問題的關鍵所在。比如對于數組：
[1,2,3,4,5,6,7]
我們依次去計算以1為結尾的子數組其和是否等于給定值，以2為結尾的子數組其和是否等于給定值，以3為結尾的子數組其和是否等于給定值。。如果有那麼記錄下該數組的長度并與之前的記錄相比較。
那麼這裡的問題是，我們怎麼能知道以比如6為結尾的子數組其和是否等于給定值呢？
讓我們來仔細的看一下這個問題，對于數組[1,2,3,4,5,6,7]，以6為結尾的子數組有多少可能性？
[1,2,3,4,5,6] [2,3,4,5,6] [3,4,5,6] [4,5,6] [5,6] [6]
可以看到有這麼多子數組，我們要一個一個的去計算每個子數組的和嗎，這不又退回之前的解法了嗎？别着急，你馬上就會明白的。
如圖所示，我們需要求解的是B，但是實際上B = C - A，是以我們又一次對問題進行了轉化，B不是很容易就能求解出來，但是對于C和A的求解就非常簡單了。
現在你應該明白了吧，對于以比如6為結尾的子數組，我們該如何計算呢？
sum(1,2,3,4,5,6) sum(1,2,3,4,5,6) - sum(1) sum(1,2,3,4,5,6) - sum(1,2) sum(1,2,3,4,5,6) - sum(1,2,3) sum(1,2,3,4,5,6) - sum(1,2,3,4) sum(1,2,3,4,5,6) - sum(1,2,3,4,5)
sum(1,2,3,4,5,6)是一個确定的值，這個非常簡單，而對于sum(1)，sum(1,2)，sum(1,2,3)，sum(1,2,3,4)，sum(1,2,3,4,5)來說我們真的有必要一個一個的去減一下嗎？當然是沒有必要的，我們可以把這些值放到一個map中，然後用sum(1,2,3,4,5,6)減去給定的值t，然後用這個值去map中查一下，如果有就說明存在這樣的一個子數組。
接下來對于sum(1)，sum(1,2)，sum(1,2,3)，sum(1,2,3,4)，sum(1,2,3,4,5)的計算也非常簡單，原因就在于對于sum(1,2,3,4,5,6)來說，sum(1,2,3,4,5,6) = sum(1,2,3,4,5) + 6，是以我們隻需要周遊一邊就能計算出所有的值，這就是累加和的概念，利用的就是前一個數組的和，本質上這也是動态規劃思想的重要特征之一，即，充分利用上一步的計算結果。
這種方法的時間複雜度為O(n)，相比最開始的O(n^3)有了很大的提高，有了這些分析就可以寫代碼了。
代碼實作
int get_length(vector<int>& arr, int target) {
if (arr.size() == 0)
return 0;
map<int,bool>m_exist;
map<int,int> m_pos;
int r = 0;
int sum = 0;
m_exist[0] = true; // 在數組的開頭放入假想的數字0
m_pos[0] = -1;
for (int i=0;i<arr.size();i++) {
sum += arr[i];
if (!m_exist[sum]) {
m_exist[sum] = true;
m_pos[sum] = i;
}
if (m_exist[sum - target])
r = max(r, i - m_pos[sum - target]);
}
return r;
}
代碼相對簡單，使用兩個map，一個map用來記錄從0開始的所有子數組的和，另一個map用來記錄對應的子數組結尾位置。注意到有這樣兩行代碼：
m_exist[0] = true;
m_pos[0] = -1;
其意圖是在數組中放入假想的0，為的就是處理這樣的一種特殊情況：假設給定數組[1,2,3]，求和為6的最長子數組，特殊之處在于該子數組的起始位置是0。
剩下的就很簡單了，僅僅就是上述分析的代碼實作，不再贅述。
問題還沒有解決完，最開始的問題是求解出奇數和偶數個數相同的最長連續子數組，有了get_length這個函數剩下的就很簡單了：
int solution(vector<int>& arr) {
if (arr.size()==0)
return 0;
for(int i=0;i<arr.size();i++){
if (arr[i] % 2 == 0)
arr[i] = 1;
else
arr[i] = -1;
}
return get_length(arr, 0);
}
将數組中偶數轉為-1，偶數轉為1，然後調用get_length函數即可。
注意，該算法的時間複雜度為O(n)，如果我們認為map的查找效率為O(1)的話。這個時間複雜度通過面試肯定是沒有問題的。
總結
對于算法問題，不要試圖“記住”問題的答案，題目千變萬化，試圖"記住"每一個算法題答案是不現實的，但是這些算法題目背後的解題思想就那麼多，你需要掌握的是解決算法問題的思維模式而不是僅僅背過幾個答案，在這個算法題目中實際上我們已經看到了這其中的一種思維模式，那就是問題的等價轉換，實際上這也是上學讀書時常用到的解題方法，對此我們都曾經爛熟于心的，這些才是值得掌握的東西而不是幾個算法題的解法，希望這個題目能給你一些啟發。
不要去“背”算法題，要有自己的方法論
更多計算機内功文章，歡迎關注微信公共賬号：碼農的荒島求生。
徹底了解作業系統系列文章
1，什麼程式？
2，程序？程式？傻傻分不清
3，程式員應如何了解記憶體：上篇
4，程式員應如何了解記憶體：下篇
計算機内功決定程式員職業生涯高度