leetcode系列
文章目錄
- 一、核心操作
- 二、外層配合操作
- 三、核心模式代碼
- 總結
去重方式和之前三數之和一樣，也可以用used數組去重，但本次嘗試使用set去重
一、核心操作
- 如果count為0了，則證明正好減到了0，就可以收獲，并返回
- 建立unordered_set
- 開始循環，如果在set中能夠搜尋到當前的數字，說明已經重復了，則直接進行下一次的循環，如果沒有找到，則說明這是一個沒有重復的新數字，將其加入set中，后面則直接進行常規操作
提示：小白個人理解，如有錯誤敬請諒解！
二、外層配合操作
- 對數組進行排序
三、核心模式代碼
代碼如下：
class Solution {
public:vector<vector<int>> res;vector<int> path;void backTracking(vector<int>& candi, int count, int startIndex){if(count==0){res.push_back(path);return;}unordered_set<int> uset;for(int i=startIndex;i<candi.size()&&(count-candi[i])>=0;i++){if(uset.find(candi[i])!=uset.end())continue;uset.insert(candi[i]);path.push_back(candi[i]);backTracking(candi,count-candi[i],i+1);path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {if(!candidates.size())return res;sort(candidates.begin(),candidates.end());backTracking(candidates,target,0);return res;}
};
總結
- 用哈希表的時間復雜度比較高，所以更常用的還是used數組或者直接用startIndex進行去重，最后在for循環條件判斷的時候，一定要進行提前預判，只有count減去當前值大于等于0才繼續進行循環，不進行提前預判剪枝的話會超時
)
