LeetCode 805. 数组的均值分割

Categories:

题目描述
思路分析
1. 解法一：子集和 DP（推荐）
相似题目

题目描述

✅ 805. 数组的均值分割

思路分析

解法一：子集和 DP（推荐）

核心思路：

设总和为 sum，若存在子集大小为 k，满足子集和为 sum * k / n 则可分割。

用 dp[k] 记录选 k 个数能得到的所有和。

逐个数更新 dp，最后检测是否存在满足条件的 k。

复杂度分析：

时间复杂度：O(n^2 * S)，其中 n 表示数组长度，S 表示可达子集和的规模。

空间复杂度：O(n * S)。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int v : nums) {
            sum += v;
        }

        List<Set<Integer>> dp = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            dp.add(new HashSet<>());
        }
        dp.get(0).add(0);

        for (int num : nums) {
            for (int k = n - 1; k >= 1; k--) {
                for (int s : dp.get(k - 1)) {
                    dp.get(k).add(s + num);
                }
            }
        }

        for (int k = 1; k < n; k++) {
            if (sum * k % n != 0) {
                continue;
            }
            int target = sum * k / n;
            if (dp.get(k).contains(target)) {
                return true;
            }
        }

        return false;
    }
}

func splitArraySameAverage(nums []int) bool {
	n := len(nums)
	sum := 0
	for _, v := range nums {
		sum += v
	}

	dp := make([]map[int]struct{}, n+1)
	dp[0] = map[int]struct{}{0: {}}

	for _, num := range nums {
		for k := n - 1; k >= 1; k-- {
			if dp[k] == nil {
				dp[k] = make(map[int]struct{})
			}
			for s := range dp[k-1] {
				dp[k][s+num] = struct{}{}
			}
		}
	}

	for k := 1; k < n; k++ {
		if sum*k%n != 0 {
			continue
		}
		target := sum * k / n
		if _, ok := dp[k][target]; ok {
			return true
		}
	}

	return false
}

相似题目

题目	难度	考察点
416. 分割等和子集	中等	子集和
494. 目标和	中等	子集和
698. 划分为k个相等的子集	中等	回溯
1049. 最后一块石头的重量 II	中等	子集和
473. 火柴拼正方形	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/21622298