6月12日 LeetCode 每日一题

三数之和

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

直接开始做有些难度，不如先做一道【两数之和】：

• 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

想到使用哈希表实现：将数组中的元素作为键储存在哈希表中，值为这个元素的位置。并且查询target-nums[i]是否在哈希表中。代码如下：

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        vector<int> ans;
        map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i)
        {
            int temp = target - nums[i];
            if (hash.count(temp))
            {
                ans.push_back(hash[temp]);
                ans.push_back(i);
                break;
            }
            hash[nums[i]] = i;
        }
        return ans;
    }
};

两数之和问题解决了，接下来解决三数问题吧。

三数问题使用哈希表似乎不太好做，使用双指针的方法：先对容器排序，然后用双指针暴力搜索数字。代码如下：

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> res;
        int len = nums.size(), left, right;
        if (len < 3)
        {
            return res;
        }
        vector<int> tmp;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < len; ++i)
        {
            if (nums[i] > 0)
            {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            left = i + 1, right = len - 1;
            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0)
                {
                    tmp = {nums[i], nums[left], nums[right]};
                    res.emplace_back(tmp);
                    while (left < right && nums[left] == nums[left + 1])
                    {
                        ++left;
                    }
                    while (left < right && nums[right] == nums[right - 1])
                    {
                        --right;
                    }
                    ++left;
                    --right;
                }
                else if (sum > 0)
                {
                    --right;
                }
                else
                {
                    ++left;
                }
            }
        }
        return res;
    }
};

问题解决。