LeetCode 1013. Partition Array Into Three Parts With Equal Sum (Java版; Easy)

爱被打了一巴掌 2023-07-13 08:12 38阅读 0赞

### [welcome to my blog][] ###

## LeetCode 1013. Partition Array Into Three Parts With Equal Sum (Java版; Easy) ##

#### 题目描述 ####

Given an array A of integers, return true if and only if we can partition the array into three non-empty parts with equal sums.
    
    Formally, we can partition the array if we can find indexes i+1 < j with 
    (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])
    
     
    
    Example 1:
    
    Input: A = [0,2,1,-6,6,-7,9,1,2,0,1]
    Output: true
    Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
    Example 2:
    
    Input: A = [0,2,1,-6,6,7,9,-1,2,0,1]
    Output: false
    Example 3:
    
    Input: A = [3,3,6,5,-2,2,5,1,-9,4]
    Output: true
    Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
     
    
    Constraints:
    
    3 <= A.length <= 50000
    -10^4 <= A[i] <= 10^4

#### 第一次做; 动动脑子, 分析一下题目; 核心: 1)每一个部分的和都得等于sum/3 ####

/* 动动脑子分析一下题目 a=b=c a+b+c=sum a=b=c=sum/3 */
    class Solution { 
        public boolean canThreePartsEqualSum(int[] A) { 
            if(A==null || A.length<3)
                return false;
            int n = A.length;
            int sum = 0;
            for(int a : A)
                sum += a;
            //寻找第一部分
            int cur=0;
            int i=0;
            for(; i<=n-3; i++){ 
                cur += A[i];
                if(cur==sum/3)
                    break;
            }
            //找不到第一部分, 返回false
            if(cur!=sum/3)
                return false;
            
            //寻找第二部分
            cur=0;
            i++;
            for(; i<=n-2; i++){ 
                cur += A[i];
                if(cur==sum/3)
                    break;
            }
            //找不到第二部分, 返回false
            if(cur!=sum/3)
                return false;
            
            
            //是否有第三部分
            return sum - cur*2 == sum/3;
        }
        
    }

#### 第一次做; 暴力; 超时50/55; 使用HashMap存储第一部分的和也会超时 ####

class Solution { 
        public boolean canThreePartsEqualSum(int[] A) { 
            if(A==null || A.length<3)
                return false;
            int n = A.length;
            int sum = 0;
            for(int a : A)
                sum += a;
            // HashMap<Integer, Integer> map = new HashMap<>();
            //i是第一部分的结尾; j是第二部分的结尾
            for(int i=0; i<=n-3; i++){ 
                int sum1 = getSum(A, 0, i);
                for(int j=i+1; j<=n-2; j++){ 
                    int sum2 = getSum(A, i+1, j);
                    int sum3 = sum - sum1 - sum2;
                    if(sum1==sum2 && sum1==sum3)
                        return true;
                }
            }
            return false;
        }
        
        private int getSum(int[] arr, int i, int j){ 
            int sum = 0;
            for(int index=i; index<=j; index++){ 
                sum += arr[index];
            }
            return sum;
        }
    }

[welcome to my blog]: https://littlehaes.com