登录
  • #刷题
  • #leetcode

同样‌‌‌‌‌‌‍‍‌‍‍‌‌‍‌‍‌‌‍‌‍‌‍‍‌‍‍‌‌‌‌‍的思路不同实现,请教为何超时

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

这是我的实现,超时:
 public int combinationSum4(int[] nums, int target) {[br][br][/br]         [br][/br][br][/br]         int[] count = new int[target + 1];[br][/br][br][/br]         return combinationSumHelper(nums, target, count);[br][/br][br][/br]    }[br][/br][br][/br]  [br][/br][br][/br]    private int combinationSumHelper(int[] candidates, int target, int[] count){[br][/br][br][/br]          if(target == 0){[br][/br][br][/br]            return 1;[br][/br][br][/br]        }[br][/br][br][/br]        if(target < 0)[br][/br][br][/br]                return 0;[br][/br][br][/br]        if(count[target] != 0)[br][/br][br][/br]                return count[target];[br][/br][br][/br]        int sum = 0;[br][/br][br][/br]        for(int i = 0; i < candidates.length; i++){[br][/br][br][/br]            sum += combinationSumHelper(candidates, target - candidates[i],count);[br][/br][br][/br]        }[br][/br][br][/br]        count[target] = sum;[br][/br][br][/br]        return count[target];[br][/br][br][/br]     }这是discuss的实现,很快跑完:[code] Map<Integer, Integer> map = new HashMap<>();[br][/br][br][/br]    public int combinationSum4(int[] nums, int target) {[br][br][/br]        int count = 0;[br][/br][br][/br]        if (nums == null || nums.length ==0 || target < 0 ) return 0;[br][/br][br][/br]        if ( target ==0 ) return 1;[br][/br][br][/br]        if (map.containsKey(target)) return map.get(target);[br][/br][br][/br]        for (int num: nums){[br][/br][br][/br]            count += combinationSum4(nums, target-num);[br][/br][br][/br]        }[br][/br][br][/br]        map.put(target, count);[br][/br][br][/br]        return count;[br][/br][br][/br]    }[/code][/i]
4条回复
热度排序

发表回复