之前写一些题比如:
    image.png
    的时候,经常用image.png
    的方式来去重,但这样有一个问题:这样去重的前提是有序数组(也就是事先排好序的)image.png

    !!!重点来了
    但在这个题中，不能惯性思维，这个题不能改变数组顺序,因此不能用类似双指针的思想来去重.本题应用哈希表去重
    image.png
    之前错误的代码：

    1. class Solution {
    2. public:
    3.     vector<vector<int>> ans;
    4.     vector<int> result;
    6.     void backtracking(vector<int>& nums, int startindex){
    7.         if(result.size() >= 2){
    8.             ans.push_back(result);
    9.         }
    11.         if(startindex >= nums.size()){
    12.             return;
    13.         }
    15.         for(int i = startindex; i < nums.size(); i++){//还要去重
    16.             if(i > startindex && nums[i] == nums[i-1]) continue;//这里有问题
    17.             if(result.size() == 0 || nums[i] >= result[result.size()-1]){
    18.                 result.push_back(nums[i]);
    19.                 backtracking(nums,i+1);
    20.                 result.pop_back();
    21.             }
    22.         }
    23.     }
    25.     vector<vector<int>> findSubsequences(vector<int>& nums) {
    26.         backtracking(nums,0);
    27.         return ans;
    28.     }   
    29. };

    正确代码：

    1. class Solution {
    2. public:
    3.     vector<vector<int>> ans;
    4.     vector<int> result;
    6.     void backtracking(vector<int>& nums, int startindex){
    7.         if(result.size() >= 2){
    8.             ans.push_back(result);
    9.         }
    11.         if(startindex >= nums.size()){
    12.             return;
    13.         }
    15.         unordered_set<int> hash;//这个哈希表每一层用
    17.         for(int i = startindex; i < nums.size(); i++){
    18.             if(!result.empty() && result.back() > nums[i] 
    19.             || hash.count(nums[i])){
    20.                 continue;
    21.             }
    22.             result.push_back(nums[i]);
    23.             hash.insert(nums[i]);
    24.             backtracking(nums,i+1);
    25.             result.pop_back();
    26.         }
    27.     }
    29.     vector<vector<int>> findSubsequences(vector<int>& nums) {
    30.         backtracking(nums,0);
    31.         return ans;
    32.     }   
    33. };

    两者去重的本质都一样:都是同一树层上不能取相同的元素
    只不过用类似双指针思想去重数组必须有序！！！

    image.png本题数据量比较小,也可以考虑用数组,这样运行速度更快。用数组的代码如下:

    1. class Solution {
    2. public:
    3.     vector<vector<int>> ans;
    4.     vector<int> result;
    6.     void backtracking(vector<int>& nums, int startindex){
    7.         if(result.size() >= 2){
    8.             ans.push_back(result);
    9.         }
    11.         if(startindex >= nums.size()){
    12.             return;
    13.         }
    15.         int hash[201] = {0};
    17.         for(int i = startindex; i < nums.size(); i++){
    18.             if(!result.empty() && result.back() > nums[i] 
    19.             || hash[100+nums[i]] == 1){
    20.                 continue;
    21.             }
    22.             result.push_back(nums[i]);
    23.             hash[nums[i]+100]++;
    24.             backtracking(nums,i+1);
    25.             result.pop_back();
    26.         }
    27.     }
    29.     vector<vector<int>> findSubsequences(vector<int>& nums) {
    30.         backtracking(nums,0);
    31.         return ans;
    32.     }   
    33. };

    image.png
    可以看到两者差异还是比较大的,数据量比较小时优先考虑用数组来模拟哈希表