30 Day Challenge Day 10 | Leetcode 701. Insert into a Binary Search Tree

题解

方法一：哈希表

一道很老的题，之前是用双指针的方法做的。不过已经隔了很久，今天再拿到的时候，受之前TwoSum的影响，思考路线一直被"哈希表"占据。完全按照 Leetcode 3. TwoSum 的做法的话会有许多重复的结果。需要想办法去重。

第一个去重是结果去重，这是保证结果正确。可以用一个 set 作为最后结果的过渡，在把每一个子数组保存到 set 中前，先排序，那么就去除重复的结果了。

到这里，已经能得到正确的结果。但在系统中会因为超时而不能通过。

第二个去重是为了去除重复的查找。这里用一个 unordered_set 来保存 nums[i]，那么就可以在遇到相同的数之后跳过，因为以此为参考数的查找已经完成过一次。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size() < 3) return {};
        
        set<vector<int>> res;
        unordered_set<int> dups;

        for(int i = 0; i < nums.size()-2; i++) {
            unordered_map<int, int> m;
            if (!dups.count(nums[i])) {
                for(int j = i+1; j < nums.size(); j++) {
                    if(m.count(-nums[i]-nums[j])) {
                        vector<int> cur({nums[i], -nums[i]-nums[j], nums[j]});
                        sort(cur.begin(), cur.end());
                        res.insert(cur);
                    }
                    m[nums[j]] = j;
                }
            }
            dups.insert(nums[i]);
        }
                
        vector<vector<int>> v;
        for(auto item : res) {
            v.push_back(item);
        }
        
        return v;
    }
};

方法二：排序 + 双指针

当然更好的办法，仍然是先给原数组排序，然后去重就方便多了。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size() < 3) return {};
        
        vector<vector<int>> res;
        
        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size()-2; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue;
            if(nums[i] > 0) continue;
            int l = i+1, r = nums.size()-1;
            while(l < r) {
                if(l > i+1 && nums[l] == nums[l-1]) {
                    l++;
                    continue;
                }
                if(nums[l]  + nums[r] == -nums[i]) {
                    res.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                } else if (nums[l]  + nums[r] < -nums[i]) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        
        return res;
    }
};