526互联

代码随想录算法训练营第二十七天 | 39. 组合总和，40.组合总和II，131.分割回文串

发布时间 2024-01-08 20:57:05作者: amulet

一、39. 组合总和

题目链接：

LeetCode 39. 组合总和

学习前：

思路：

无

学习后：

思路：

  • 需要额外定义的成员变量：
private List<List<Integer>> res;
private List<Integer> list;
  • 调用函数：
List<List<Integer>> combinationSum(int[] candidates, int target) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    Arrays.sort(candidates);
    fun(candidates,target,0);
    return res;
}
  • 返回类型和参数：
void fun(int[] candidates, int target, int start)
  • 终止条件：
if (target==0) {
    res.add(new ArrayList<>(list));
    return;
}
  • 单次遍历内容
for (int i = start; i < candidates.length; i++) {
    if(target-candidates[i]<0)return;
    target-=candidates[i];
    list.add(candidates[i]);
    fun(candidates,target,i);
    target+=candidates[i];
    list.remove(list.size()-1);
}

时间复杂度：O(n*2^n)

空间复杂度：O(n)

二、40.组合总和II

题目链接：

LeetCode 40.组合总和II

学习前：

思路：

  • 需要额外定义的成员变量：
private List<List<Integer>> res;
private List<Integer> list;
  • 调用函数：
List<List<Integer>> combinationSum(int[] candidates, int target) {
    res = new ArrayList<>();
    list = new ArrayList<>();
    Arrays.sort(candidates);
    fun(candidates,target,0);
    return res;
}
  • 返回类型和参数：
void fun(int[] candidates, int target, int start)
  • 终止条件：
if (target==0) {
    res.add(new ArrayList<>(list));
    return;
}
  • 单次遍历内容
for (int i = start; i < candidates.length; i++) {
    if(i>start && candidates[i]==candidates[i-1]) continue;
    if(target-candidates[i]<0)return;
    target-=candidates[i];
    list.add(candidates[i]);
    fun(candidates,target,i+1);
    target+=candidates[i];
    list.remove(list.size()-1);
}

时间复杂度：O(n*2^n)

空间复杂度：O(n)

学习后：

加深理解

三、131.分割回文串

题目链接：

LeetCode 131.分割回文串

学习前：

思路：

待补

学习后：

待补

四、学习总结

  1. 时间：1h
  2. 第一题和第二题的区别在于第二题需要去重