荣成市信用建设网站,手机商场网站制作,东莞机电学校网站建设与管理,辽宁建设工程信息网业绩录入阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路
此题一看应该就是需要用到动态规划算法#xff0c;假设我们以 f[d]表示总和为 d 的元素组合的个数#xff0c;首先#xff0c;我们遍历 nums 数组#xff0c;
如果有 nums[i] target#xff0c;那么组… 阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路
此题一看应该就是需要用到动态规划算法假设我们以 f[d]表示总和为 d 的元素组合的个数首先我们遍历 nums 数组
如果有 nums[i] target那么组合中第一个元素我们放置 nums[i]组合中余下元素的排列总个数也就变成了子问题 f[target - nums[i]]。
如果有 nums[i] target那么组合中只能放置 nums[i]这一个元素。
3. 代码实现
于是我开始实现了第一版代码完全就照着上面的解题思路来写使用递归。
class Solution {
public:int combinationSum4(vectorint nums, int target) {int ret 0;for (int i 0; i nums.size(); i) {if (nums[i] target) {ret combinationSum4(nums, target-nums[i]);}else if (nums[i] target) {ret 1;}}return ret;}
};很可惜没有通过全部测试用例超时了。 超出时间限制 10 / 16 个通过的测试用例 这里计算 f[target - nums[i]]的时候有可能存在大量重复比如nums[1, 2, 3, 4], target5第一个元素我们放置 2 时需要计算 f(3)。然后如果前两个元素我们都放置 1 时也需要计算 f(3)。
所以一个很自然的思路就是把已经计算过的 f(d)记录下来下次遇到可以直接用。
class Solution {
public:int combinationSum4(vectorint nums, int target) {static vectorint target_ret(1001, -1);int ret 0;for (int i 0; i nums.size(); i) {if (nums[i] target) {int left target - nums[i];if (target_ret[left] -1) {target_ret[left] combinationSum4(nums, left); }ret target_ret[left];}else if (nums[i] target) {ret 1;}}return ret;}
};于是我定义了一个静态数组全部初始化为 -1计算一个 f(d) 后就把它记录下来下次直接使用不用再递归去调用一次函数。
但是这次直接变成解答错误了。我把错误的用例单独拿出来测试答案是对的。去网上一查原来 LeetCode 会用这同一个类去测试所有的测试用例那么我的静态数组就会受到前一个测试用例的影响所以答案也就是错的了此路看来也不通
那就只能手动递推了因为我们最终要计算 f(target) 而 f(target) 可能依赖于 f(target-1)、f(target-2)....f(1)所以我们就从 1 开始一个一个往后计算 f(d) 即可。
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint target_ret(target1, 0);for (int j 1; j target; j) {for (int i 0; i nums.size(); i) {if (nums[i] j) {int left j - nums[i];target_ret[j] target_ret[left];}else if (nums[i] j) {target_ret[j] 1;}}}return target_ret[target];}
};很不幸还是出错了看起来是整型数超出表示范围了一个简单的思路是把 int 换成 unsigned int终于成功了 Line 16: Char 35: runtime error: signed integer overflow: 2147483647 1 cannot be represented in type ‘int’ (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:25:35 class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorunsigned int target_ret(target1, 0);for (int j 1; j target; j) {for (int i 0; i nums.size(); i) {if (nums[i] j) {int left j - nums[i];target_ret[j] target_ret[left];}else if (nums[i] j) {target_ret[j] 1;}}}return target_ret[target];}
};要细究为什么会越界的话其实题目描述里特别说明了 题目数据保证答案符合 32 位整数范围。 但是这里只是说 f(target) 不会越界我们从 1 遍历到 target 的某个中间变量可能越界了然后这个中间变量实际上是用不到的。
比如nums[2, 6, 9], target15 f(14) 是不会用到的但是我们也会计算它。
时间复杂度为 O ( t a r g e t ∗ n u m s . s i z e ( ) ) O(target*nums.size()) O(target∗nums.size())空间复杂度为 O ( t a r g e t ) O(target) O(target)。
如果数组中存在负数的话会存在一个包含正数和负数的序列它们的和为 0也就是说可以无限添加这个序列而和保持不变这样f(target) 就是无穷的了。
