[每日一题系列] LeetCode 1013. 将数组分成和相等的三个部分

题目：

给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum

题解：先遍历一边数组，得到总和，然后求除3的值（avg），如果除不尽，当然直接返回false；然后定义左右两个用来做双指针的整数变量和存左右两部分和值的变量，同时往中间搜索，如果中间没有空间了（没有第三部分）也是false；两边都分出等于avg的值了，中间如果等于avg就是true，不等于就是false；

代码：

class Solution {

    public boolean canThreePartsEqualSum(int[] A) {

        int avg = 0;

        for (int t:A)

            avg+=t;

        if (avg%3 != 0)

            return false;

        avg /=3;

        int l_sum = 0;

        int r_sum = 0;

        int lp = 0;

        int rp = A.length-1;

        while (lp<=rp){

            if (l_sum!=avg || lp == 0){

                l_sum+=A[lp];

                lp++;

            }

            if (r_sum!=avg || rp == A.length-1){

                r_sum+=A[rp];

                rp--;

            }

            if (l_sum == avg && r_sum == avg && lp<=rp)

            {

                int m_sum = 0;

                for (int i = lp; i <= rp; i++)

                    m_sum+=A[i];

                if (m_sum == avg)

                    return true;

                else

                    return false;

            }

        }

        return false;

    }

}

巴特西

[每日一题系列] LeetCode 1013. 将数组分成和相等的三个部分

最新文章

热门文章