如何删除网站的信息吗,pc端自定义页设计与制作模板,wamp做的网站标签图标,免费行情软件app网站大全下载安装Leetcode 416.分割等和子集
题目描述
给定一个非负整数的数组 nums #xff0c;你需要将该数组分割成两个子集#xff0c;使得两个子集的元素和相等。如果可以分割#xff0c;返回 true #xff0c;否则返回 false。
示例 1#xff1a; 输入#xff1a;nums [1,5,11,…Leetcode 416.分割等和子集
题目描述
给定一个非负整数的数组 nums 你需要将该数组分割成两个子集使得两个子集的元素和相等。如果可以分割返回 true 否则返回 false。
示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11]
Java 实现代码
public class Solution {public boolean canPartition(int[] nums) {int sum 0;for (int num : nums) {sum num;}// 如果总和是奇数不能平分if (sum % 2 ! 0) {return false;}int target sum / 2;boolean[] dp new boolean[target 1];dp[0] true; // 和为 0 总是能做到for (int num : nums) {// 从后往前更新 dp 数组for (int j target; j num; j--) {dp[j] dp[j] || dp[j - num];}}return dp[target];}
}解题思路 这个问题可以转化为0/1背包问题我们需要检查是否能在数组中找到一个子集使得这个子集的和为 sum(nums) / 2。如果可以找到剩下的元素自然就是另一个子集两者和相等。 具体步骤 首先检查数组总和是否为偶数。如果总和为奇数直接返回 false因为无法将其平均分配成两个相等的部分。 动态规划定义一个布尔数组 dp其中 dp[i] 表示是否能够从数组中选取若干个元素使得它们的和为 i。初始化时dp[0] true因为和为 0 总是可以通过选择空集合得到。 遍历数组中的每个元素对于每个元素从后往前更新 dp 数组。如果 dp[j - num] 为 true则说明可以通过添加 num 这个元素使得和为 j所以设置 dp[j] true。 最终判断 dp[target] 是否为 true其中 target sum(nums) / 2。 复杂度分析 时间复杂度O(n * target)其中 n 是数组 nums 的长度target 是目标值即 sum(nums) / 2。需要遍历每个元素并且对于每个元素更新 dp 数组的每个状态。 空间复杂度O(target)我们只需要一个大小为 target 1 的布尔数组 dp 来存储状态。 执行过程示例 假设 nums [1, 5, 11, 5]。 计算数组总和sum 1 5 11 5 22所以目标是 target sum / 2 11。 初始化 dp 数组dp[0] true其余元素初始化为 false。 dp [true, false, false, false, false, false, false, false, false, false, false, false] 遍历数组元素更新 dp 数组 处理元素 1 dp[1] true // 可以通过选择 1 得到和 1
dp [true, true, false, false, false, false, false, false, false, false, false, false]处理元素 5 dp[6] true // 可以通过选择 5 得到和 6
dp[5] true // 可以通过选择 5 得到和 5
dp [true, true, false, false, false, true, true, false, false, false, false, false]处理元素 11 dp[11] true // 可以通过选择 11 得到和 11
dp [true, true, false, false, false, true, true, false, false, false, false, true]处理元素 5 dp[10] true // 可以通过选择 5 得到和 10
dp[5] true // 可以通过选择 5 得到和 5
dp [true, true, false, false, false, true, true, false, false, false, true, true]最终dp[11] 为 true说明可以分割成两个和为 11 的子集因此返回 true。
