15. 三数之和

暴力搜索

• 时间复杂度 O(n^3)，空间复杂度 O(1)

哈希表

• 由于需要找到具体某一个数，所以考虑使用哈希表
• 又因每个数字可能出现不止一次，故采用计数哈希
• 每个组合内，同一数字只可以使用一次，但可以出现相同数字，不需要重复组合
• 步骤
  1. 以每个数为 key，value 为 1，建立哈希表，如果数重复出现，value + 1
  2. 遍历哈希表的 key
     1. 正在遍历的 key 的 value-1，遍历修改后的哈希表的 key，其 value-1
     2. 使用 0 - (两个获得到的 key 之和)，在哈希表中查找结果，如果找到 key 且其 value 不为 0，则三个 key，否则继续遍历
  3. 删除已遍历的 key，继续遍历未遍历的 key
• 时间复杂度：哈希表 O(n) + 两层遍历 O(n^2)，即 O(n^2)。新建哈希表，空间复杂度 O(n)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int, int> hashMap{};
        for (auto i : nums)
        {
            if (!hashMap.try_emplace(i, 1).second)
            {  // Already has the element
                hashMap[i] = hashMap[i] + 1;
            }
        }

        vector<vector<int>> result{};
        for (auto i = hashMap.begin(); i != hashMap.cend();)
        {
            i->second--;
            auto hashMapInner = hashMap;
            if (i->second <= 0)
            {
                hashMapInner.erase(i->first);
            }
            for (auto j = hashMapInner.begin(); j != hashMapInner.cend();)
            {
                j->second--;
                auto lastNum = hashMapInner.find(0 - i->first - j->first);
                if (lastNum != hashMapInner.cend() && lastNum->second > 0)
                {
                    result.emplace_back(vector<int>{i->first, j->first, lastNum->first});
                }
                j = hashMapInner.erase(j);
            }
            i = hashMap.erase(i);
        }
        return result;
    }
};

• 超时未通过
  Time Limit Exceeded
  312/312 cases passed (N/A)

优化

• 不复制哈希表

排序 + 双指针

• 排序
• 遍历数组，当前位置 i，每次将左右指针从数组两端开始，为 left，right
• 如果 left + i + right > 0，right--，反之 left++
• 时间复杂度 O(n^2)，如果在原数组上排序，空间复杂度为 O(logn)，如需新建排序数组，则为 O(n)