哈希表部分的最后一节，三数之和比较难，而且用哈希表实现效率不高，使用双指针可以获得较好的时间效率。

1 赎金信

1.1 题目描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

1.2 思路解析

通过构造字符和出现次数的unordered_map即可。

1
2
3
4
5
6
7
8
9
10
11
bool canConstruct(string ransomNote, string magazine) {
        // 构造字母-次数的映射键值对
        unordered_map<char,int> m{0};
        for (char c:magazine)
            m[c]++;
        for (char c:ransomNote)
        {
            if(--m[c] < 0)  return false;
        }
        return true;   
    }

2 三数之和

2.1 题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

2.2 思路解析

这个题首先得知道怎么找全三个和为0的数，首先可以用减治的思想化为定值 + 两数之和的问题，之前我们已经用时间复杂度为O($n$)的方法求解过两数之和的问题了，加上固定指针的最外层循环，就可以实现时间复杂度为$O(n^2)$的算法了。

但是问题来了，找出全部的三元组之后要如何去重呢？

我想到的方法是利用set的模版以及自动去重的特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
vector<vector<int>> twoSum(int target, const vector<int>& nums, int k){
        vector<vector<int>> ans;
        multiset<int> s;
        for(int i = k; i < nums.size(); i++){
            
            auto f = s.find(target - nums[i]);
            if (f == s.end()){
                s.insert(nums[i]);
            }else {
                ans.push_back({-1 * target, *f, nums[i]});
            }
        }
        return ans;
    }


    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        set<vector<int>> ans;
        vector<vector<int>> ansVec;
        for (int i = 0; i < nums.size(); i++){
            // if (i > 0 && nums[i] == nums[i - 1]) continue;
            vector<vector<int>> t = twoSum(-1 * nums[i], nums, i+1);
            for (const auto& vec:t){
                ans.insert(vec);
            }
        }
        ansVec.reserve(ans.size());
        for (const auto& vec:ans){
                ansVec.push_back(vec);
            }
        return ansVec;
    }

这种方法虽然正确，但是提交的时候却超时了，我们加上这一句剪枝操作试试。

1
if (i > 0 && nums[i] == nums[i - 1]) continue;

加上之后就可以顺利通过测试了，但是所用的时间和空间还是太大。分析其中的原因，虽然算法整体的时间复杂度是$O(n^2)$，但是建立哈希表的时间太慢，而这是使用哈希方法不可避免的问题。

那有没有比哈希表更高效的方法呢？

有的，答案就是使用双指针！

哈希表实现中，确定好第一个指针之后，每移动一次第二个指针都会调用哈希函数在红黑树中建立一个节点。这在时间和空间上都会有加大的开销。于是我们想，如果能够用两个指针相反方向遍历剩余数组，找到合适的target值，这样时间和空间开销就会小很多了！

于是我们构造两个指针，left和right指针来进行遍历。如果三个数加起来是负数的话，left指针就往右移；如果加起来是正数的话，right指针就往左移。然后再加上去重操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int i = 0; i < nums.size();i++){
            if (i > 0 && nums[i] == nums[i-1])  continue;
            int l = i + 1, r = nums.size() - 1;
            while (l < r){
                if (nums[i] + nums[l] + nums[r] < 0)
                    l++;
                else if (nums[i] + nums[l] + nums[r] > 0)
                    r--;
                else if (nums[l] == nums[l-1] && r != nums.size() - 1 && nums[r] == nums[r+1])   {
                    l++;r--;  // 如果上次push_back时l++与r--的结果还是一样的，那么跳过这个结果
                }
                else{
                    ans.push_back({nums[i], nums[l++],nums[r--]}); // while循环还要进行下去，因为可能还有三元组没有找到，所以用continue
                    continue;  
                }
            }
        }
        return ans;
    }

用这种方法，时间复杂度就很小，算法性能提升了很多。