leetcode 927. Three Equal Parts | 927. 三等分（Java）

痛定思痛。 2022-08-30 01:58 133阅读 0赞

## 题目 ##

[https://leetcode.com/problems/three-equal-parts/][https_leetcode.com_problems_three-equal-parts]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

不知道为什么是 hard，感觉这道题没有套路（印象中这几道 hard 都没有什么套路，这就是 hard 的原因吗），甚至没有 get 到这题的难点是什么，大概是在考察分析问题的能力吧。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

分析完之后，思路很简单。先算总共有多少个 1，就可以分离出右边的部分了。然后根据右边的部分，匹配出左边部分和中间部分。

class Solution { 
        public int[] threeEqualParts(int[] arr) { 
            int leftEnd, midEnd, rightBegin;
            // 统计每个相同部分中1的个数
            int count = 0;
            for (int n : arr)
                count += n;
            if (count == 0) return new int[]{ 0, arr.length - 1};
            if (count % 3 != 0) return new int[]{ -1, -1};
            count /= 3;
            // 分离最后一个部分
            int cnt = 0;
            int i;
            for (i = arr.length - 1; cnt < count; i--) { 
                cnt += arr[i];
            }
            rightBegin = i + 1;
            // 分离第一个部分，并验证其与最后一个部分相同
            i = 0;
            while (arr[i] != 1) i++;
            int j = rightBegin;
            while (j < arr.length) { 
                if (arr[i++] != arr[j++]) return new int[]{ -1, -1};
            }
            // 分离中间部分，并验证其与最后一个部分相同
            leftEnd = i - 1;
            while (arr[i] != 1) i++;
            j = rightBegin;
            while (j < arr.length) { 
                if (arr[i++] != arr[j++]) return new int[]{ -1, -1};
            }
            midEnd = i;
            return new int[]{ leftEnd, midEnd};
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_three-equal-parts]: https://leetcode.com/problems/three-equal-parts/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/842a1aa201844ee7933e62ca9b0e014c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/a934a7e38f8541cf98405d726d767bdb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/538e4cde33984ce5a6d11f8a4c7f493a.png