【代码随想录 | Leetcode | 第十天】哈希表 | 三数之和 | 四数之和

我会带着你远行 2023-10-13 21:14 19阅读 0赞

## 前言 ##

**欢迎来到[小K][K]的[Leetcode|代码随想录|专题化][Leetcode]专栏，今天将为大家带来哈希法~三数之和 | 四数之和的分享**✨

#### 目录 ####

*  前言
 *  15. 三数之和
 *  18. 四数之和
 *  总结

--------------------

## 15. 三数之和 ##

✨[题目链接点这里][Link 1]  
**给你一个整数数组 nums ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]`满足`i != j、i != k 且 j != k`，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。**

示例 1：  
**输入**：nums = \[-1,0,1,2,-1,-4\]  
**输出**：\[\[-1,-1,2\],\[-1,0,1\]\]  
**解释**：  
nums\[0\] + nums\[1\] + nums\[2\] = (-1) + 0 + 1 = 0 。  
nums\[1\] + nums\[2\] + nums\[4\] = 0 + 1 + (-1) = 0 。  
nums\[0\] + nums\[3\] + nums\[4\] = (-1) + 2 + (-1) = 0 。  
**不同的三元组是 \[-1,0,1\] 和 \[-1,-1,2\] 。  
注意，输出的顺序和三元组的顺序并不重要。**

示例 2：  
**输入**：nums = \[0,1,1\]  
**输出**：\[\]  
**解释：唯一可能的三元组和不为 0 。**

示例 3：  
**输入**：nums = \[0,0,0\]  
**输出**：\[\[0,0,0\]\]  
**解释：唯一可能的三元组和为 0 。**

提示：  
3 <= `nums.length` <= 3000  
\-105 <= `nums[i]`<= 105

**「方法一」：哈希法，直接两层`for`循环确定第一个和第二个数，然后在哈希表中查找最后一个数，思路没有问题，但是实现起来很困难，就是去重的问题和时间复杂度的问题，去重主要是第二个数的去重【因为数组已经排序，如果连续的三个数字相同，那么它们组成的三元组只能是一种情况，不需要重复计算】，第二个就是时间复杂度的问题，这个真不好解决，只能注意去重的细节，因为本身就有两个for循环，在加上erase和insert操作~我这里是险过**

class Solution {
        
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
        
            vector<vector<int>> result;
            sort(nums.begin() , nums.end());
            for (int i = 0; i<nums.size(); i++) {
        
                if (nums[i] > 0) break;
                if (i > 0 && nums[i] == nums[i-1]) continue;
                unordered_set<int> set;
                for (int j = i + 1; j < nums.size(); j++) {
        
                    if (j > i + 2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2]) continue;
                    int c = - (nums[i] + nums[j]);
                    if (set.find(c) != set.end()) {
        
                        result.push_back({
        nums[i] , nums[j] , c});
                        set.erase(c);
                    }
                    else set.insert(nums[j]);
                }
            }
            return result;
        }
    };

![在这里插入图片描述][acbd23d980284819b88f55d15abf0a4a.png]

**「方法二」：双指针法**  
![在这里插入图片描述][a012cda933794b588ce46f2ce87a5239.gif]

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums\[i\]，b = nums\[left\]，c = nums\[right\]。

接下来如何移动left 和right呢， 如果nums\[i\] + nums\[left\] + nums\[right\] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums\[i\] + nums\[left\] + nums\[right\] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

Tips：这里说答案中不可以包含重复的三元组，并不是说三元组中不能有重复元素，但是重复元素不能是同一位置，**所以这里去重使用的是`nums[i] == nums[i-1]`，而不是`nums[i] == nums[i+1]`**

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

![在这里插入图片描述][8ffbb8f33e784b3b8a1dbe2ca47490ab.png]

## 18. 四数之和 ##

✨[题目链接点这里][Link 2]  
**给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组`[nums[a], nums[b], nums[c], nums[d]]`（若两个四元组元素一一对应，则认为两个四元组重复）：`0 <= a, b, c, d < n；a、b、c 和 d`互不相同`nums[a] + nums[b] + nums[c] + nums[d] == target`你可以按 任意顺序 返回答案 。**

示例 1：  
**输入**：nums = \[1,0,-1,0,-2,2\], target = 0  
**输出**：\[\[-2,-1,1,2\],\[-2,0,0,2\],\[-1,0,0,1\]\]

示例 2：  
**输入**：nums = \[2,2,2,2,2\], target = 8  
**输出**：\[\[2,2,2,2\]\]

提示：  
1 <=`nums.length` <= 200  
\-109 <= `nums[i]` <= 109  
\-109 <= `target` <= 109

**使用双指针，和上一题思路一样，只是多加了一层`for`循环**

class Solution {
        
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
        
            vector<vector<int>> result;
            sort(nums.begin() , nums.end());
            for (int k = 0; k < nums.size(); k++) {
        
                if (nums[k] > target && nums[k] >= 0) break;
                if (k > 0 && nums[k] == nums[k-1]) continue;
                for (int i = k + 1; i < nums.size(); i++) {
        
                    if (nums[k] + nums[i] > target && nums[k] + nums[i] >=0 ) break;
                    if (i > k + 1 && nums[i] == nums[i-1]) continue;
                    int left = i + 1;
                    int right = nums.size() - 1;
                    while (left < right) {
        
                        if (nums[k] + nums[i] > target - nums[left] - nums[right]) right--;
                        else if (nums[k] + nums[i] < target - nums[left] - nums[right]) left++;
                        else {
        
                            result.push_back({
        nums[k] , nums[i] , nums[left] , nums[right]});
                            while (left < right && nums[right] == nums[right-1]) right--;
                            while (left < right && nums[left] == nums[left+1]) left++;
                            left++ , right--; 
                        }
                    }
                }
            }
            return result;
        }
    };

![在这里插入图片描述][ceb5e8633c4241b0b36b9afd892a35e7.png]

## 总结 ##

**要恰当使用哈希法，并根据实际情况选择合适的结构（数组，set，map）**

[K]: https://blog.csdn.net/qq_72157449?spm=1000.2115.3001.5343
[Leetcode]: https://blog.csdn.net/qq_72157449/category_12293229.html?spm=1001.2014.3001.5482
[Link 1]: https://leetcode.cn/problems/3sum/description/
[acbd23d980284819b88f55d15abf0a4a.png]: https://img-blog.csdnimg.cn/acbd23d980284819b88f55d15abf0a4a.png
[a012cda933794b588ce46f2ce87a5239.gif]: https://img-blog.csdnimg.cn/a012cda933794b588ce46f2ce87a5239.gif
[8ffbb8f33e784b3b8a1dbe2ca47490ab.png]: https://img-blog.csdnimg.cn/8ffbb8f33e784b3b8a1dbe2ca47490ab.png
[Link 2]: https://leetcode.cn/problems/4sum/
[ceb5e8633c4241b0b36b9afd892a35e7.png]: https://img-blog.csdnimg.cn/ceb5e8633c4241b0b36b9afd892a35e7.png