Algorithms & Data Structures : Leetcode 927. Three Equal Parts

題目：

Three Equal Parts - LeetCode

少數不看 hint 寫出來的 hard 題，但其實也算是賽到的，在複雜度上是 TLE 的。想了兩個小時，也才想了一個 O(N^2) 的解法。。。。看了一下 Leetcode 官方的詳解，這題是可以 O(N) 的。

醜解法：

Runtime: 480 ms
Memory Usage: 484.3 MB

觀察： 右邊的部分，就算增加長度，也有可能不會增加數的大小。左邊的部分，則是增加長度後一定會增加數的大小。

於是每次優先增加右邊，等右邊的數有變之後，再來增加左邊的長度。

左右邊的長度相同，且數也相同，再來比較中間的數。

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {        
        vector<int> v;
        vector<int> ans = vector<int>(2, -1);
        int left = 0;
        int right = arr.size() - 1;
        
        string sl;
        string real_sr;
        string sr;
        string sm;
bool f = true;
        for(int i = 0;i < arr.size();i++) {
            if(arr[i] != 0) {
                f = false;
                break;
            }
        }
        if(f) {
            ans[0] = 0;
            ans[1] = arr.size() - 1;
            return ans;
        }
        
        
        
        while(left < arr.size()) {
            if(arr[left] == 0) {
                
            } else {
                sl = "1";
                break;
            }
            left++;
        }
        
        while(right > left) {
            if(arr[right] == 0) {
                real_sr = "0" + real_sr;
            } else {
                real_sr = "1" + real_sr;
                sr = real_sr;
                break;
            }
            
            if(sr == sl) {
                break;
            }
            right--;
        }
for(int i = left + 1;i < right;i++) {
            if(sm.size() == 0 && arr[i] == 0) {
                
            } else if(arr[i] == 1){
                sm += "1";
            } else if(arr[i] == 0) {
                sm += "0";
            }
        }
        
        
        while(left < right) {
            
            
            if(sl == sr) { 
                sm.clear();
                for(int i = left + 1;i < right;i++) {
                    if(sm.size() == 0 && arr[i] == 0) {
                
                    } else if(arr[i] == 1) {
                        sm += "1";
                    } else if(arr[i] == 0) {
                        sm += "0";
                    }
                }
                if(sl == sm) {
                   return {left, right};
                }
            }
            
            right--;
            if(arr[right] == 0) {
                real_sr = "0" + real_sr;
            } else {
                real_sr = "1" + real_sr;
                sr = real_sr;
                    
                while(sl.size() < sr.size()) {
                    left++;
                    if(arr[left] == 0) {
                        sl += "0";
                    } else {
                        sl += "1";
                    }
                }
            }
        }        
        return ans;
    }
};

Leetcode 詳解的想法：

我想得太複雜了。。。詳解的想法就簡易很多。
首先因為三個部份的 binary 表示法相同，所以大家的 1 會一樣多。

1. 取得三個部份的 1 ，取第一個 1 的 index 以及最後一個 1 的 index
2. 取得三個部份的 1 的後綴 0 個數
3. 有以上資訊可還原三個部份的數 ( 以 binary 陣列表示 )

4. 此時可比較三個部分是否相同

複雜度 O(N)，太神啦。