网站内链设置,济南官网,网店代运营的套路,江苏机械加工网题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
示例 1#xff1a;
输入#xff1a; nums [1,5,11,5] 输出#xff1a; true 解释#xff1a; 数组可以分割成 [1, 5, 5] 和 [11…题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入 nums [1,5,11,5] 输出 true 解释 数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2
输入 nums [1,2,3,5] 输出 false **解释**数组不能分割成两个元素和相等的子集。
提示
1 nums.length 2001 nums[i] 100
代码及注释
func canPartition(nums []int) bool {res : 0// 计算数组 nums 的总和for i : 0; i len(nums); i {res nums[i]}// 如果总和为奇数不能分割成等和子集直接返回 falseif res % 2 1 {return false}// 将总和除以2问题转化为是否存在和为 res/2 的子集res / 2// 初始化一个动态规划数组dp[i] 表示是否存在和为 i 的子集dp : make([]bool, res 1)dp[0] true// 遍历 nums 数组更新 dp 数组for _, num : range nums {for j : res; j num; j-- {dp[j] dp[j] || dp[j - num]}}// 返回 dp[res]return dp[res]
}代码解释 计算数组总和 for i : 0; i len(nums); i {res nums[i]
}这里通过循环计算数组 nums 的总和。 检查总和是否为奇数 if res % 2 1 {return false
}如果数组 nums 的总和 res 是奇数那么不能将其分割成两个和相等的子集直接返回 false。 将总和除以2 res / 2将总和 res 除以 2问题转化为是否存在和为 res/2 的子集。 动态规划 dp : make([]bool, res 1)
dp[0] true
for _, num : range nums {for j : res; j num; j-- {dp[j] dp[j] || dp[j - num]}
}
return dp[res]初始化一个动态规划数组 dp其中 dp[i] 表示是否存在和为 i 的子集。遍历 nums 数组并更新 dp 数组 dp[j] dp[j] || dp[j - num] 表示对于每一个数字 num如果存在和为 j - num 的子集那么存在和为 j 的子集。 返回结果 return dp[res]返回 dp[res]判断是否存在和为 res 的子集即是否可以将数组 nums 分割成两个和相等的子集。
这种方法的时间复杂度是 O(n x target}其中 n 是数组 nums 的长度target 是数组 nums 的总和的一半。
