【算法挨揍日记】day04——15. 三数之和、18. 四数之和

超、凢脫俗 2024-03-03 08:07 37阅读 0赞

![3392f00852754ce2b9642d8b99505f70.png][]

## 15. 三数之和 ##

[15. 三数之和![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/069a0e0b3a5c48a782cbbd7dd6b581a1.png][15. _icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_leetcode.cn_problems_3sum]

### 题目描述： ###

给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请你返回所有和为 `0` 且不重复的三元组。

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

![ef4379ad038d4130af3b8115950f645d.png][]

### 解题思路： ###

> 我们先来看看题目：题目要求a+b+c=0，并且a、b、c三个数的下标各不相同，并且返回所有的可能性，并且要去重
> 
> ![649c126d74394b8aa30beb746964b055.png][]
> 
> 我们首先可以确定一下大体思路：sort排序（有序）,有序可以被双指针或者二分来运用，这里我们使用排序+双指针
> 
> ![8edd9ded2c3f41bbb0d0a34b43d7c7c2.png][]
> 
> 我们这里是三数之和，我们可以确定一个cur下标来遍历数组，一次一个数，然后问题就变成了剩下的数组的两数之和的问题！
> 
> ![6249270c71234ba2bd6e7c6da718b5a1.png][]
> 
> 我们两数之和就可以就可以运用双指针来降时间复杂度，left和right从两边到中间
> 
> 这里比较考察大家的是left和right的边界问题，这里非常容易越界！！！
> 
> 我们来结合本题的部分代码来理解
> 
> 我们整个红色区域可以划分为\[begin,right\]（这里就不用left和right避免混乱，这里的begin代表红色的第一个，end是红色区域的最后一个的下一个），我们正常来说left<end，right>0的，但是我们这边下标访问涉及到left+1和right-1，所以left需要比end少一，也就是让left+1最大到end-1的位置，同理right>1
> 
> ![04bbaff2d8dd448eb752f9b71a0206e2.png][]

### 解题代码： ###

class Solution {
    public:
           vector<vector<int>> threeSum(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> nnums;
            int size = nums.size();
            int cur = 0;
            while (cur < size - 1)
            {
                int left = cur + 1;
                int right = size - 1;
                int a = (-1) * nums[cur];//找到两数之和为a的两个值
                while (left < right)
                {
                    if (nums[left] + nums[right] == a)
                    {
                        nnums.push_back({ nums[cur],nums[left],nums[right] });
                        while (right > 1 && nums[right] == nums[right - 1])
                            right--;
                        right--;
                    }
                    else if (nums[left] + nums[right] > a)
                    {
                        while (right > 1 && nums[right] == nums[right - 1])
                            right--;
                        right--;
                    }
                    else if (nums[left] + nums[right] < a)
                    {
                        while (left<size-1&&nums[left] == nums[left + 1])
                            left++;
                        left++;
                    }
                }
                while (cur<size-1&&nums[cur] == nums[cur + 1])
                    cur++;
                cur++;
    
            }
            return nnums;
        }
    };

## 18. 四数之和 ##

[18. 四数之和![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/dedb302813584a32b41c1c3d47d828c4.png][18. _icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_leetcode.cn_problems_4sum]

### 题目描述: ###

给你一个由 `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`

你可以按 **任意顺序** 返回答案 。

![b628d941682141e1b0f377161ecf35a4.png][]

### 解题思路： ###

本题与上题一样，就是在三数之和的基础上外面再套一层

### 解题代码： ###

class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            sort(nums.begin(), nums.end());
            int size = nums.size();
            vector<vector<int>>nnums;
            for (int i = 0; i < nums.size();)
            {
                int cur = i+1;
                while (cur < size - 1)
                {
                    int left = cur + 1;
                    int right = size - 1;
                    long long a = (long long)target-nums[i] - nums[cur];//找到两数之和为a的两个值
                    while (left < right)
                    {
                        if (nums[left] + nums[right] == a)
                        {
                            nnums.push_back({ nums[i],nums[cur],nums[left],nums[right] });
                            while (right > 1 && nums[right] == nums[right - 1])
                                right--;
                            right--;
                        }
                        else if (nums[left] + nums[right] > a)
                        {
                            while (right > 1 && nums[right] == nums[right - 1])
                                right--;
                            right--;
                        }
                        else if (nums[left] + nums[right] < a)
                        {
                            while (left < size - 1 && nums[left] == nums[left + 1])
                                left++;
                            left++;
                        }
                    }
                    while (cur < size - 1 && nums[cur] == nums[cur + 1])
                        cur++;
                    cur++;
                }
    
                while (i < size - 1 && nums[i] == nums[i + 1])
                    i++;
                i++;
            }
            return nnums;
        }
    };

### ![fc5f61986d7140c7b0699856aaf4d829.gif][] ###

[3392f00852754ce2b9642d8b99505f70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/b59c49797c4843ef8980f849716df071.png
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[15. _icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_leetcode.cn_problems_3sum]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/069a0e0b3a5c48a782cbbd7dd6b581a1.png
[ef4379ad038d4130af3b8115950f645d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/37379293fa584a0c8d8be94c861f5136.png
[649c126d74394b8aa30beb746964b055.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/1ca259d0de8b4729b37a337358bb84f0.png
[8edd9ded2c3f41bbb0d0a34b43d7c7c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/f8fe5a36360a4b94aab1bbed46cebb60.png
[6249270c71234ba2bd6e7c6da718b5a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/a7f96b8430a047b0bafb990459429143.png
[04bbaff2d8dd448eb752f9b71a0206e2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/67aade1fefb140a4b1df828a6fa0ecbd.png
[18. _icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_leetcode.cn_problems_4sum]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/dedb302813584a32b41c1c3d47d828c4.png
[b628d941682141e1b0f377161ecf35a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/4f4426cf7d884dfa81e02629626bcde2.png
[fc5f61986d7140c7b0699856aaf4d829.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/f976fb8f971c4a25af7bff52b9505331.png