LeetCode之旅──696.計數二進制子串

題目：給定一個字符串 s，計算具有相同數量0和1的非空(連續)子字符串的數量，並且這些子字符串中的所有0和所有1都是組合在一起的。
重復出現的子串要計算它們出現的次數。

示例：

輸入: "00110011"
輸出: 6
解釋: 有6個子串具有相同數量的連續1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

請注意，一些重復出現的子串要計算它們出現的次數。

另外，“00110011”不是有效的子串，因為所有的0（和1）沒有組合在一起。

最先想用棧來解決，但發現行不通。然後慢慢發現規律了，我們可以用一個指針對準第一個數字的起點（最先是0），然後用另一個指針對準另一個數字的起點（如示例中第一個1的位置），然後兩個指針一起跑，只要它們對應位置的值不相等，那答案就加1。值相等後必然是其中一個數字跑完了，可以根據和前一個位置對比得出是跑在前面的指針跑完了還是跑在後面的，如果是前面的先跑完了就讓後面的指針直接跑到下一個起點（即前面的指針本次的起點），接著開始下一輪，直到有一個指針到達末尾。

好吧上面一段其實並不用看，我們只需要將相同的數字看作一組，然後遍歷每組的數字個數組成的數組，相鄰元素取最小值，加起來就得到結果了。比如示例的數組為[2, 2, 2, 2]，相鄰取最小再加起來就是6。

其實理論上說兩個方法是差不多的，後者像是前者的抽象化。我們刷算法題總是容易下意識的用人類思維思考，然後用計算機去“模擬”，所以經常會遇到將思維轉化為代碼時不流暢和容易出錯。我認為所謂算法思想，就是一種將人類思維抽象成計算機思維的能力。