【LeetCode】Day183-数组的均值分割

题目

805. 数组的均值分割【困难】

题解

设nums数组的平均数为avg=nums/n，我们移动k个元素到数组A中，则此时数组A的平均数也为avg，sum(A)=k*avg
该问题等价为从数组中选出k个数，使得k个数之和为k*avg，即转化为0-1背包问题（从书包里取k件物品，使得背包重量为k*avg）

1. 状态定义：dp[i][x] 表示从nums数组中取出 i 个数，加和为 x 的可能性，为true表示可以，false表示不可能。
2. 状态转移方程：假如当前遍历到nums[j]，那么dp[i+1][nums[j]+x]=dp[i][x]
   根据题目条件，sum(A)/k=nums/n，转化为sum(A)=sum(nums)*k/n，则找到一个满足条件的A即可
3. 初始条件：dp[0][0]=true
4. 返回值：有一个dp[i][sum(nums)/2]=ture即认为可均值分割

but！如果直接利用递推公式求解时间会超限，因此需要一些剪枝技巧

• 既然sum(A)=sum(nums)*k/n，那么如果$sum(nums)\ast k\%n==0$ (前式sum(A)有解），则说明存在这样的A，如果不存在这样的A则可以提前终止
• 既然nums可以划分为A,B两个数组，那么一定有一个数组的长度<=n/2，只要检查小的数组满不满足subsum*n==sum(nums)*k即可

class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n=nums.length,m=n/2;
        if(n==1)
            return false;
        //计算sum
        int sum=0;
        for(int num:nums)
            sum+=num;
        //剪枝
        boolean possible=false;
        for(int i=1;i<=n;i++){
            if(sum*i%n==0){
                possible=true;
                break;
            }
        }
        //数组A不存在，可以提前终止
        if(!possible)
            return false;
        //初始化dp
        Set<Integer>[] dp=new Set[m+1];
        for(int i=0;i<=m;i++)
            dp[i]=new HashSet<>();//dp存每种长度的子集和
        dp[0].add(0);
        //计算dp
        for(int num:nums){
            for(int i=m;i>=1;i--){//k
                for(int x:dp[i-1]){//i-1个元素的sum
                    int curr=x+num;//当前i个元素的sum(A)
                    if(curr*n==sum*i)//存在满足条件的A
                        return true;
                    dp[i].add(curr);//sum(A)加进dp[i]
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间复杂度：$O(n^2\ast sum(nums))$

空间复杂度：$O(n\ast sum(nums))$，一共有 n 种长度的子集，每种长度的子集和最多有 sum(nums) 个。