(C++)四数之和--双指针法

简介: (C++)四数之和--双指针法

个人主页:Lei宝啊

愿所有美好如期而遇


该题目链接:

前言:

做这道题之前建议先看一下这道题目:三数之和,思路很相似。


算法原理:

双指针法,不一定是说就要使用指针,只是一种形象的说法,在数组中,我们一般将数组下标当做指针。

这道题我们仍然延续之前的思路,固定一个数,去遍历剩下的三个数和是否等于target-固定数,这样剩下的就是三数之和,再固定一个数,去看剩下的两个数和是否等于target-固定数1-固定数2,如果相等,那么就将这两个数以及固定数尾插进vector<vector<int>>,然后去重,我们要去三次重,两个数相等尾插后去重,固定数2去重,固定数1去重。

图示:

后面的情况不再往下画。

代码:

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


目录
相关文章
|
NoSQL Redis
Redis下Lua脚本的复制模式
假设我们的Redis选择了主从架构, 和AOF持久化方式。我们执行一条写命令时, 该条命令会被发送到从服务器, 和追加到AOF文件中。当我们执行的不是一条命令, 而是Lua脚本时, 默认情况下, 整个Lua脚本的内容会进行复制, 但是存在一些特殊情况。
2431 0
Redis下Lua脚本的复制模式
|
Go API Docker
热门go与微服务15
热门go与微服务15
73 2
|
机器学习/深度学习 算法 计算机视觉
基于深度学习网络的USB摄像头实时视频采集与人脸检测matlab仿真
**摘要 (Markdown格式):** ```markdown - 📹 使用USB摄像头(Tttttttttttttt666)实时视频检测,展示基于YOLOv2在MATLAB2022a的实施效果: ``` Tttttttttttttt1111111111------------5555555555 ``` - 📺 程序核心利用MATLAB视频采集配置及工具箱(Dddddddddddddd),实现图像采集与人脸定位。 - 🧠 YOLOv2算法概览:通过S×S网格预测边界框(B个/网格),含坐标、类别概率和置信度,高效检测人脸。
|
Linux 应用服务中间件 nginx
Linux 快速搭建 Overleaf 5.0 附中文字体及完整 TexLive 安装教程(2024最新版)
2024最新版 Linux 极速安装 Overleaf 5.0 手把手教学!附 XeLatex 修复,新增中文字体以及安装完整版 TexLive 教程!
|
机器学习/深度学习 缓存 数据可视化
Vim编辑器
认识一下Vim编辑器
187 4
Vim编辑器
|
Python
【python】习题 1-5周(下)
【python】习题 1-5周(下)
125 0
解决ERROR in Conflict: Multiple assets emit different content to the same filename index.html 的问题
解决ERROR in Conflict: Multiple assets emit different content to the same filename index.html 的问题
1057 0
|
XML 存储 前端开发
2022最新前端经典面试试题
2022最新前端经典面试试题
105 0
|
XML JSON 前端开发
一文读懂Java Web是什么?
Java Web应用开发是基于Jakarta EE技术平台的。Jakarta EE是企业级应用的解决方案。Jakarta EE框架提供的Web开发技术主要支持两类软件的开发:一类是Web应用服务器(Web Application Server);另一类是在Web应用服务器上运行的Web应用程序(Web Application)。本系列推文介绍的Java Web应用开发就是第二类,即在Web应用服务器上运行的Web应用程序的开发。 Java Web是使用Java技术解决Web相关领域开发问题的技术栈。开发一个完整的Java Web项目涉及静态Web资源、动态Web资源以及项目的部署。
673 0
一文读懂Java Web是什么?
|
C语言
c 语言 无参无返函数,函数的调用
函数:c语言模块编程的核心语法。 作用:将代码按照功能划分为一段一段的独立的代码,有利于代码的管理,调试,维护。
215 1