同样的思路不同实现，请教为何超时

在做combination sumIV（lc377） 时候, 我用了数组来记录以前计算过的次数， discuss 有人用了map来存，代码基本一样，但是我的超时了， 他的却很快跑完。 IDE 测试了下我的也跑了很久跑不完，请教一下原因，代码贴在下面了，谢谢各位解答：
这是我的实现，超时：

1. public int combinationSum4(int[] nums, int target) {
   
2.          
   
3.          int[] count = new int[target + 1];
   
4.          return combinationSumHelper(nums, target, count);
   
5.     }
   
6.   
   
7.     private int combinationSumHelper(int[] candidates, int target, int[] count){
   
8.           if(target == 0){
   
9.             return 1;
   
10.         }
    
11.         if(target < 0)
    
12.                 return 0;
    
13.         if(count[target] != 0)
    
14.                 return count[target];
    
15.         int sum = 0;
    
16.         for(int i = 0; i < candidates.length; i++){
    
17.             sum += combinationSumHelper(candidates, target - candidates[i],count);
    
18.         }
    
19.         count[target] = sum;
    
20.         return count[target];
    
21.      }

复制代码

这是discuss的实现，很快跑完：

1. Map<Integer, Integer> map = new HashMap<>();
   
2.     public int combinationSum4(int[] nums, int target) {
   
3.         int count = 0;
   
4.         if (nums == null || nums.length ==0 || target < 0 ) return 0;
   
5.         if ( target ==0 ) return 1;
   
6.         if (map.containsKey(target)) return map.get(target);
   
7.         for (int num: nums){
   
8.             count += combinationSum4(nums, target-num);
   
9.         }
   
10.         map.put(target, count);
    
11.         return count;
    
12.     }

复制代码

个人理解是，因为 int[] 的初始化值本来就是 0 ，但同时在你的代码中如果 target < 0 (当前 sum 超了)，也会返回 0，对于 sum > target 的情况下并没有实现完全的 “记忆化搜索”，后面的计算中遇到 sum > target 的重复子问题不会立刻返回原来的结果，而是重算一遍，所以超时了。

我把你的代码粘贴到 leetcode 上，对于 int[] count 做了 Arrays.fill(count, -1) 然后 dfs 中以是否为 -1 为标准判断当前子问题是否计算过，就 AC 了~ 17个test case 用时 1ms
----

编辑纠正下，是相对于所有已经计算过但是解的个数 = 0 的子问题，当前代码都会重复计算，不单单是 sum > target 的情况

mnmunknown 发表于 2016-8-2 21:15
个人理解是，因为 int[] 的初始化值本来就是 0 ，但同时在你的代码中如果 target < 0 (当前 sum 超了)，也 ...

多谢解答哈， coin change 也是一样实现， 然后竟然过了所有test， 看来上一题test case 不够大

mnmunknown 发表于 2016-8-2 21:15
个人理解是，因为 int[] 的初始化值本来就是 0 ，但同时在你的代码中如果 target < 0 (当前 sum 超了)，也 ...

仔细看了下， 还是有个问题， 第二段代码用map也是一个思路赋值， 但是确可以啊。。

wujingzhishui 发表于 2016-8-3 08:55
仔细看了下， 还是有个问题， 第二段代码用map也是一个思路赋值， 但是确可以啊。。

map 不一样啊~ java 里新开一个 int[] array 默认里面填的都是 0 ，只靠某个位置上的值是不是 0 无法确定这个 sum 到底有没有计算过；但是 HashMap 新开之后不会默认你有这个 key，肯定是 put 进去的，containsKey 如果 返回 true 就说明这个子问题之前肯定计算过了。