Day 20。
今天两道题分别是 Combination Sum II 和 First Missing Positive。
一道是 回溯去重题，一道是 数组原地哈希题。

今天的关键词：排序、同层去重、回溯、原地映射、下标哈希、最小缺失正数。

🧠 LeetCode 40 – Combination Sum II

💡 思路总结

这题和之前的 Combination Sum 很像，还是在找和为 target 的所有组合。
但这题多了两个关键限制：

  • 每个数字只能用一次
  • 结果中不能有重复组合

所以这题的重点就变成了：

回溯 + 去重

你的思路很对，先排序，再在回溯过程中做去重控制。

💻 代码实现

class Solution {
    //多了个去重
    //拿在开始时进行一个排序就行了

public:
    vector<int> path;
    vector<vector<int>> result;
    //回溯
    void dfs(vector<int>& candidates, int target,int sum,int pos){
        if(sum == target){
            result.push_back(path);
            return;
        }
        else if(sum > target){
            return;
        }
        else{
            for (int i =pos;i< candidates.size();i++){
                if (i > pos && candidates[i] == candidates[i - 1]) continue;
                path.push_back(candidates[i]);
                dfs(candidates,target,sum+candidates[i],i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates,target,0,0);
        return result;
    }
};

📌 知识点总结

1️⃣ 和 LeetCode 39 的区别

这题和 Combination Sum 的最大区别有两个：

题目是否可重复使用当前元素是否需要去重
LeetCode 39可以不强调重复值输入
LeetCode 40不可以需要

所以这里递归时写的是：

dfs(candidates, target, sum + candidates[i], i + 1);

而不是 i。
这就表示：

当前元素选过之后，下一层只能从后面继续选，不能再选自己。

2️⃣ 排序是去重前提

你一开始先排序：

sort(candidates.begin(), candidates.end());

这是非常关键的一步。
因为只有排序之后，相同元素才会挨在一起，后面的去重条件才成立。

3️⃣ 这句是灵魂：同层去重

if (i > pos && candidates[i] == candidates[i - 1]) continue;

这句一定要理解透。

它的意思不是“整个搜索树都不能重复”，而是：

同一层里，如果当前数字和前一个数字相同，就跳过

为什么是 i > pos？

因为：

  • pos 表示这一层的起点
  • 如果 i > pos 且和前一个数一样，说明这一层已经选过这个值了
  • 再选只会产生重复组合

这就是经典的：

同层去重，而不是同枝去重

4️⃣ 回溯框架还是那一套

这题虽然多了去重，但整体框架和之前一样：

选择

path.push_back(candidates[i]);

递归

dfs(candidates,target,sum+candidates[i],i+1);

撤销选择

path.pop_back();

你会发现，回溯题变来变去，骨架其实很稳定。
变化主要在于：

  • 能不能重复选
  • 要不要去重
  • 剪枝条件是什么

5️⃣ 还能继续剪枝

你现在这版已经很好了。
因为数组已经排序，后面其实还能加一个小优化：

如果当前：

sum + candidates[i] > target

那后面更大的数也一定不行了，可以直接 break。
这样剪枝会更早。

不过就当前阶段来说，先把“排序 + 同层去重”的核心思想吃透更重要。

🔥 LeetCode 41 – First Missing Positive

💡 思路总结

这题是非常经典的一道 hard。
要求找出数组中第一个缺失的正整数，而且要求：

  • 时间复杂度 O(n)
  • 额外空间复杂度 O(1)

这就意味着：

  • 不能排序
  • 不能开哈希表

所以这题真正的核心是：

把数组本身当成哈希表来用

你的思路就是经典正解：

原地哈希 / 原地映射

💻 代码实现

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //原地哈希
        //答案在[0-nums.size()+1]之间，那就做固定的映射
        int n = nums.size();
        for(int i = 0;i < n ;i++){
            while(nums[i] > 0 && nums[i] < n+1 && nums[nums[i]-1] != nums[i] ){
                swap(nums[i],nums[nums[i]-1]);
            }
        }
        for(int j = 0; j < n;j++){
            if(nums[j] != j+1 )return j+1;
        }
        return n+1;
    }
};

📌 知识点总结

1️⃣ 为什么答案只会在 1 ~ n+1

这是这题最关键的结论之一。

假设数组长度是 n，那么第一个缺失的正整数只可能是：

1, 2, 3, ..., n+1

比如：

  • 如果 1 ~ n 都在，那答案就是 n+1
  • 否则答案一定在前面这些数里

正因为这个范围固定，我们才可以做“下标映射”。

2️⃣ 映射规则非常漂亮

你这里的核心思想是：

如果数字 x 合法，就把它放到下标 x-1 的位置

也就是说：

1 放到 nums[0]
2 放到 nums[1]
3 放到 nums[2]
...

这样如果最后数组变成：

[1, 2, 3, 4]

说明前 4 个正整数都在。
如果某个位置不对，比如：

nums[2] != 3

那答案就是 3。

3️⃣ 为什么要用 while 而不是 if

这一句是灵魂：

while(nums[i] > 0 && nums[i] < n+1 && nums[nums[i]-1] != nums[i])

因为一次交换后，当前位置 nums[i] 可能还是一个应该继续放置的合法数。
所以必须不断交换，直到：

  • 当前数不合法
  • 或者已经放到了正确位置
  • 或者目标位置已经有相同数字

这就是“连环归位”的感觉。

4️⃣ 条件判断很讲究

你这里判断：

nums[i] > 0 && nums[i] < n+1

就是在筛掉无用数字：

  • 负数没用
  • 0 没用
  • 大于 n 的数也没用

因为我们只关心 1 ~ n 这些位置能不能对上。

5️⃣ 最后扫描就是找答案

归位结束后，再扫一遍：

if(nums[j] != j+1 ) return j+1;

含义非常明确：

  • 理想情况下，位置 j 上应该放 j+1
  • 如果不是，说明 j+1 缺失

如果全部都对上了，那说明：

return n+1;

🧩 今日总结

题目核心思想
LeetCode 40排序 + 回溯 + 同层去重
LeetCode 41原地哈希 + 下标映射 + 连环交换

今天两题都很有代表性：

  • 40 是回溯题里非常经典的“去重版本”
  • 41 是数组题里非常经典的“原地哈希版本”

🧠 今日收获

今天最值得记住的两个模型：

1. 回溯去重模型

如果题目里：

  • 有重复元素
  • 结果不能重复

那就要想到：

  • 先排序
  • 同层去重
  • 小心区分 i 和 i+1

2. 原地哈希模型

如果题目要求：

  • O(n)
  • O(1) 额外空间
  • 数值范围和数组长度有关

那很可能要想到：

把数组下标当作哈希位置

这是数组 hard 题里非常高频的一种思维。

💬 写给自己的话

Day 20 了。

二十天了。

你现在已经不只是刷基础题了，
而是在慢慢接触那些真正很有代表性的“经典模型题”：

  • 回溯怎么去重
  • 数组怎么原地哈希
  • 什么时候该排序
  • 什么时候该利用下标做映射

这些东西，才是真正能拉开差距的地方。

别急着觉得 hard 难。
很多 hard 题其实不是知识特别新，而是更考验你：

能不能把已有的技巧组合起来。

你现在就在这个路上。

继续写，继续练，继续总结。
Day 20，不只是打卡数字漂亮，而是说明你真的在稳定进步。

阿玉，Day 20，继续冲。

—— 刷题第 20 天