leetcode 组合总和 java(看不懂就推导几遍)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 组合总和 java(看不懂就推导几遍),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1470字,纯文字阅读大概需要3分钟。
内容图文
![leetcode 组合总和 java(看不懂就推导几遍)](/upload/InfoBanner/zyjiaocheng/827/ed5387660bf5461796044ecab35108c8.jpg)
给定一个无重复元素的数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的数字可以无限制重复被选取。
说明:
- 所有数字(包括
target
)都是正整数。 - 解集不能包含重复的组合。
示例 1:
输入: candidates =[2,3,6,7],
target =7
, 所求解集为: [ [7], [2,2,3] ]
示例 2:
输入: candidates = [2,3,5],
target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
成功
执行用时 : 8 ms, 在Combination Sum的Java提交中击败了86.85% 的用户
内存消耗 : 38.1 MB, 在Combination Sum的Java提交中击败了93.62% 的用户
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<List<Integer> >();
if(candidates.length ==0 || candidates[0]>target)
return res;
List<Integer> tmp = new ArrayList<Integer>();
helper(candidates, target, 0, tmp, res);
return res;
}
public void helper(int[] a, int target, int start, List<Integer> tmp, List<List<Integer>> res){
if (target < 0){
return;
}
if(target == 0){
res.add(new ArrayList<Integer>(tmp));
//res.add(tmp);//得到的是空结果,因为tmp仅仅是一个指针
return;
}
for(int i=start; i<a.length; i++){
tmp.add(a[i]);
//target = target -a[i];不新建int出错
//helper(a, target, i, tmp, res);
int newtarget = target -a[i];
helper(a, newtarget, i, tmp, res);
tmp.remove(tmp.size()-1 );
if(newtarget<0)
break;
}
}
}
if(newtarget<0)
break;
有了这句从20ms直接提速到8ms。也就是说当和已经超过target值时,我们无需再遍历更大的元素。
内容总结
以上是互联网集市为您收集整理的leetcode 组合总和 java(看不懂就推导几遍)全部内容,希望文章能够帮你解决leetcode 组合总和 java(看不懂就推导几遍)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。