算法每日双题精讲——双指针（三数之和，四数之和）

首先对数组进行排序，这一步骤至关重要，它能为后续的判断和指针移动提供便利。
遍历排序后的数组，对于每个元素 nums [i]，将其视为三元组中的第一个数。
接着，定义两个指针 left = i + 1 和 right = nums.length - 1，分别指向 i 的下一个元素和数组的末尾。
计算 nums [i] + nums [left] + nums [right] 的值，并与目标值 0 进行比较。
如果和等于 0，说明找到了满足条件的三元组，将其加入结果集。同时，为了避免重复结果，需要移动指针跳过重复元素。
如果和小于 0，说明当前和较小，需要将 left 指针向右移动一位，以增大和的值。
如果和大于 0，说明当前和较大，需要将 right 指针向左移动一位，以减小和的值。

🙋这个解题思路是怎么来的呢？

我们首先最容易想到解法一：暴力求解

👇以下是优化的算法：

我们在上篇文章中已经做过，和为S的俩个数，因此本题可以转换为nums[left]+nums[right]= - nums[a]，这样思路就明朗起来了。

画图如下：

此时的target=-nums[a]=4 -4+6<4,让left++

-1+6>4,让right--

-1+5=4，记录数组，并让left--，right++

❗注意：

代码实现（C++ 为例）：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 对输入的向量进行排序，为后续使用双指针法做准备
        sort(nums.begin(), nums.end());
        int n = nums.size();
        // 用于存储最终结果的二维向量
        vector<vector<int>> ret;
        int a = 0;
        while (a < n) {
            // 左指针从当前固定数的下一个位置开始
            int left = a + 1;
            // 右指针指向向量末尾
            int right = n - 1;
            // 计算目标值，即当前固定数的相反数，因为要找三数之和为零
            int target = (-1) * nums[a];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target) {
                    // 如果两数之和大于目标值，右指针左移
                    right--;
                } else if (sum < target) {
                    // 如果两数之和小于目标值，左指针右移
                    left++;
                } else {
                    // 找到满足三数之和为零的三元组，将其加入结果向量
                    ret.push_back({nums[a], nums[left], nums[right]});
                    // 跳过重复的左指针值
                    while (left < right && nums[left] == nums[++left]) {}
                    // 跳过重复的右指针值
                    while (left < right && nums[right] == nums[--right]) {}
                }
            }
            // 跳过重复的固定数
            a++;
            while (a + 1 < n && nums[a] == nums[a - 1]) {
                a++;
            }
        }
        return ret;
    }
};

👀时间复杂度和空间复杂度

时间复杂度：排序的时间复杂度为 $O(nlogn)$ ，遍历数组的时间复杂度为 $O(n^2)$ ，总体时间复杂度为 $O(n^2)$ 。
空间复杂度：代码中除了结果集外，只使用了有限的几个变量，不随输入规模增长，所以空间复杂度为 $O(1)$ ，不考虑结果集的空间占用。

💯四数之和

题目链接👉【力扣】

题目描述：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c，d ，使得 a + b + c + d = target ？找出所有满足条件且不重复的四元组。

⭐解题思路：

同样先对数组进行排序。
遍历排序后的数组，对于每个元素 nums [i]，将其视为四元组中的第一个数。
对于每个 nums [i]，再次遍历其后的元素 nums [j]（j > i），将其视为四元组中的第二个数。
然后定义两个指针 left = j + 1 和 right = nums.length - 1，分别指向 j 的下一个元素和数组的末尾。
计算 nums [i] + nums [j] + nums [left] + nums [right] 的值，并与目标值 target 进行比较。
如果和等于 target，说明找到了满足条件的四元组，将其加入结果集。同样要注意跳过重复元素。
如果和小于 target，将 left 指针向右移动一位。
如果和大于 target，将 right 指针向左移动一位。

🙋这个解题思路是怎么来的呢？

我们首先最容易想到解法一：暴力求解

👇以下是优化的算法：

排序加双指针

和上面的方法一样，不过要多套一层循环，让b也移动，目标值变成了target-nums[a]-nums[b]

代码实现（C++ 为例）：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // 获取输入向量的长度
        int n = nums.size();
        // 用于存储最终结果的二维向量
        vector<vector<int>> ret;
        // 初始化第一个指针 a，用于外层循环遍历输入向量
        int a = 0;
        // 对输入向量进行排序，以便后续使用双指针法进行查找
        sort(nums.begin(), nums.end());
        while (a < n) {
            // 初始化第二个指针 b，用于内层循环，固定第二个数
            int b = a + 1;
            while (b < n) {
                // 初始化两个指针 left 和 right，用于在固定前两个数的情况下，使用双指针法寻找另外两个数
                int left = b + 1;
                int right = n - 1;
                while (left < right) {
                    // 计算剩余两个数的目标和
                    long long t = (long)target - nums[a] - nums[b];
                    // 计算当前两个指针所指元素之和
                    int sum = nums[left] + nums[right];
                    if (sum > t) {
                        // 如果和大于目标值，右指针左移
                        right--;
                    } else if (sum < t) {
                        // 如果和小于目标值，左指针右移
                        left++;
                    } else {
                        // 如果和等于目标值，找到满足条件的四元组，将其加入结果向量
                        ret.push_back({nums[a], nums[b], nums[left], nums[right]});
                        // 移动指针，继续寻找下一个可能的四元组
                        left++;
                        right--;
                        // 跳过重复的 left 指针值
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        // 跳过重复的 right 指针值
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }
                // 移动 b 指针，跳过重复的值
                b++;
                while (b < n && nums[b] == nums[b - 1]) {
                    b++;
                }
            }
            // 移动 a 指针，跳过重复的值
            a++;
            while (a < n && nums[a] == nums[a - 1]) {
                a++;
            }
        }
        return ret;
    }
};

👀时间复杂度和空间复杂度

时间复杂度：排序的时间复杂度为 $O(nlogn)$ ，两层循环遍历数组的时间复杂度为 $O(n^3)$ ，总体时间复杂度为 $O(n^3)$ 。
空间复杂度：同样，不考虑结果集的空间占用，代码中只使用了有限的几个变量，空间复杂度为 $O(1)$ 。

💯总结

✍通过对 “三数之和” 和 “四数之和” 这两道题目的深入探究，我们更加深刻地领悟到了双指针算法在处理数组组合问题时的卓越效能。它巧妙地利用数组的有序性，通过指针的灵活移动，高效地查找满足条件的元素组合，避免了复杂的多层嵌套循环。希望大家在今后的算法学习过程中，能够熟练掌握双指针技巧，在算法的世界中畅游无阻。

我将持续在算法领域深耕细作，为大家带来更多精彩的算法知识讲解与问题解析。欢迎大家关注我

👉【A Charmer】

原文地址：https://blog.csdn.net/2301_82213854/article/details/143660388

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：《Python网络安全项目实战》项目3 处理文件中的数据_练习题（3）
下一篇：yolov8涨点系列之替换DW卷积

Python用CEEMDAN-LSTM-VMD金融股价数据预测及SVR、AR、HAR对比可视化
全文链接：https://tecdat.cn/?p=38224分析师：Duqiao Han股票市场是一个复杂的非线性系统，股价受到许多经济和社会因素的影响。因此，传统的线性或近线性预测模型很难有效、准
阅读更多2024-11-14
【redis】—— 环境搭建教程
redis在Linux下进行安装
阅读更多2024-11-14
国内AI工具复现GPTs效果详解
GPTs系列模型是由OpenAI公司开发的一系列基于Transformer架构的预训练语言模型。自2018年GPT-1问世以来，GPTs系列模型经历了多次迭代，每次迭代都在模型规模、训练数据、算法优化
阅读更多2024-11-14
【MySQL从入门到放弃】InnoDB磁盘结构(一)
篇幅原因，本文只解析了InnoDB磁盘结构中的表空间、数据字典、双写缓冲区，对他们的功能、分类等做了细致分析，并对数据的双写流程做了解析。下一篇我们继续把剩下的重做日志、撤销日志、二进制日志做一个全面
阅读更多2024-11-14
MySQL Workbench导入数据比mysql命令行慢
包含2812979条数据的csv文件。
阅读更多2024-11-14
二叉树面试题（C 语言）
本文讲述了 8 道与二叉树有关的面试题，均给出了题目OJ链接、解题思路和相应代码。
阅读更多2024-11-14
内网域环境、工作组、局域网等探针方案
systeminfo 详细信息net start 启动服务tasklist 进程列表schtasks 计划任务（受权限影响）了解当前服务器的网络接口信息，为判
阅读更多2024-11-14
模拟实现优先级队列
模拟实现优先级队列PriorityQueue。
阅读更多2024-11-14
Java | Leetcode Java题解之第559题N叉树的最大深度
Java | Leetcode Java题解之第559题N叉树的最大深度
阅读更多2024-11-14
vue3 ts项目结合vant4 复选框+气泡弹框实现一个类似Select样式的下拉选择功能
const warnNameList = ref([modelSystem(GetPrecent(1000, 1500), '模型名称'), modelSystem(GetPrecent(1500,
阅读更多2024-11-14

算法每日双题精讲——双指针（三数之和，四数之和）

💯前言

💯三数之和

题目描述：

⭐解题思路：

🙋这个解题思路是怎么来的呢？

代码实现（C++ 为例）：

👀时间复杂度和空间复杂度

💯四数之和

题目描述：

⭐解题思路：

🙋这个解题思路是怎么来的呢？

代码实现（C++ 为例）：

👀时间复杂度和空间复杂度

💯总结

相关文章