【算法专题--双指针算法】leecode-15.三数之和（medium）、leecode-18. 四数之和（medium）

🍁你好，我是 RO-BERRY
📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识
🎄感谢你的陪伴与支持 ，故事既有了开头，就要画上一个完美的句号，让我们一起加油

在这里插入图片描述

目录

  • 前言
  • 1. 三数之和
  • 2. 解法（排序+双指针）：
  • 3. 四数之和（medium）
  • 4. 解法（排序 + 双指针）

前言

双指针
常见的双指针有两种形式，一种是对撞指针，⼀种是左右指针。
对撞指针：一般用于顺序结构中，也称左右指针。

  • 对撞指针从两端向中间移动。一个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
  • 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
    • left == right （两个指针指向同一个位置）
    • left > right （两个指针错开）

快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。

快慢指针的实现方式有很多种，最常用的⼀种就是：

  • 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

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

2. 解法（排序+双指针）：

算法思路：

本题与两数之和类似，是非常经典的面试题。
与两数之和稍微不同的是，题目中要求找到所有「不重复」的三元组。那我们可以利用在两数之和那里用的双指针思想，来对我们的暴力枚举做优化：

  1. 先排序；
  2. 然后固定⼀个数 a ：
  3. 在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于 -a 即可。

但是要注意的是，这道题里面需要有「去重」操作~

  1. 找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
  2. 当使用完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素

算法流程：

先将 nums 排序，时间复杂度为 O(NlogN)。

固定 333 个指针中最左（最小）元素的指针 k，双指针 i，j 分设在数组索引 (k,len(nums))(k, len(nums))(k,len(nums)) 两端。

双指针 iii , jjj 交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：

  1. 当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 3 个元素都大于 0 ，在此固定指针 k 之后不可能再找到结果了。
  2. 当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
    3.i，j分设在数组索引 (k,len(nums))两端，当i < j时循环计算sum = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：

  • 当s < 0时，i += 1并跳过所有重复的nums[i]；

  • 当s > 0时，j -= 1并跳过所有重复的nums[j]；

  • 当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合。

C++代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n;) // 固定数 a
        {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) 
            {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else 
                {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++, right--;
                    // 去重操作 left 和 right
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重 i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

在这里插入图片描述
Java代码：

class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) // 固定数 a
        {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else
                {
                    // nums[i] nums[left] num[right]
                     ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                     left++; right--; // 缩⼩区间继续寻找
                     // 去重：left right
                     while (left < right && nums[left] == nums[left - 1]) left++;
                     while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重：i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
}

在这里插入图片描述

3. 四数之和（medium）

题目描述：

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

4. 解法（排序 + 双指针）

前置题目:
请先完成三数之和。

思路:
思路和三数之和 一样，排序后，枚举 nums[a]作为第一个数，枚举 nums[b] 作为第二个数，那么问题变成找到另外两个数，使得这四个数的和等于 target，这可以用双指针解决。
对于 nums[a] 的枚举：

  1. 设 s=nums[a]+nums[a+1]+nums[a+2]+nums[a+3]。如果 s>targets，由于数组已经排序，后面无论怎么选，选出的四个数的和不会比 s 还小，所以后面不会找到等于 target的四数之和了。所以只要 s>targets ，就可以直接 break 外层循环了。

  2. 设 s=nums[a]+nums[n−3]+nums[n−2]+nums[n−1]。如果 s<targets ，由于数组已经排序，nums[a]加上后面任意三个数都不会超过 s，所以无法在后面找到另外三个数与 nums[a]相加等于 target。但是后面还有更大的 nums[a]，可能出现四数之和等于 target 的情况，所以还需要继续枚举，continue 外层循环。

  3. 如果 a>0且 nums[a]=nums[a−1]，那么 nums[a] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue 外层循环。（可以放在循环开头判断。）

对于 nums[b] 的枚举（b 从 a+1 开始），也同样有类似优化：

  1. 设 s=nums[a]+nums[b]+nums[b+1]+nums[b+2]。如果 s>targets，由于数组已经排序，后面无论怎么选，选出的四个数的和不会比 s 还小，所以后面不会找到等于 target 的四数之和了。所以只要 s>targets ，就可以直接 break。

  2. 设 s=nums[a]+nums[b]+nums[n−2]+nums[n−1]。如果 s<targets，由于数组已经排序，nums[a]+nums[b] 加上后面任意两个数都不会超过 s，所以无法在后面找到另外两个数与 nums[a] 和 nums[b] 相加等于 target。但是后面还有更大的 nums[b]，可能出现四数之和等于 target 的情况，所以还需要继续枚举，continue。

  3. 如果 b>a+1b>a+1b>a+1 且 nums[b]=nums[b−1]，那么 nums[b]\textit{nums}[b]nums[b] 和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接 continue。注意这里 b>a+1 的判断是必须的，如果不判断，对于示例 2 这样的数据，会直接 continue，漏掉符合要求的答案。

对于 Java/C++ 等语言，注意相加结果可能会超过 32 位整数范围，需要用 64 位整数存储四数之和。

思路来自灵茶山艾府

C++代码：

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 利⽤ 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim) left++;
                    else if (sum > aim) right--;
                    else
                    {
                        ret.push_back({ nums[i], nums[j], nums[left++],
                       nums[right--] });
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

在这里插入图片描述
Java代码：

class Solution
{
    public List<List<Integer>> fourSum(int[] nums, int target)
    {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long aim = (long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > aim) right--;
                    else if (sum < aim) left++;
                    else
                    {
                        ret.add(Arrays.asList(nums[i], nums[j], nums[left++],
                            nums[right--]));
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
}

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/488223.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

龙蜥 Anolis OS 7.9 一键安装 Oracle 11GR2（231017）单机版

龙蜥 Anolis OS 7.9 一键安装 Oracle 11GR2（231017）单机版

前言 Oracle 一键安装脚本&#xff0c;演示 龙蜥 Anolis OS 7.9 一键安装 Oracle 11GR2&#xff08;231017&#xff09;单机版过程&#xff08;全程无需人工干预&#xff09;&#xff1a;&#xff08;脚本包括 ORALCE PSU/OJVM 等补丁自动安装&#xff09; ⭐️ 脚本下载地址…
阅读更多...
【编译tingsboard】出现gradle-maven-plugin:1.0.11:invoke (default)

【编译tingsboard】出现gradle-maven-plugin:1.0.11:invoke (default)

出现的错误&#xff1a; [ERROR] Failed to execute goal org.thingsboard:gradle-maven-plugin:1.0.11:invoke (default) on project http: Execution default of goal org.thingsboard:gradle-maven-plugin:1.0.11:invoke failed: Plugin org.thingsboard:gradle-maven-plugi…
阅读更多...
uni-app框架（项目创建）

uni-app框架（项目创建）

1.学习说明 dcloud官方除uni-app外&#xff0c;还有新生的uni-app x&#xff08;即下一代uni-app&#xff09;&#xff0c;如果是初学者或者刚入门同学&#xff0c;建议还是使用uni-app进行开发。 无论是vue还是uni&#xff0c;作为前端开发的一个框架学习方法是一致的&#…
阅读更多...
了解一波经典的 I/O 模型

了解一波经典的 I/O 模型

最近读了波网络 I/O 相关的文章&#xff0c;做下总结、摘录。&#xff08;未完&#xff09; 经典 I/O 模型 {% checkbox red checked, 阻塞式 I/O&#xff08;blocking I/O&#xff09; %}{% checkbox red checked, 非阻塞式 I/O&#xff08;non-blocking I/O&#xff09; %}…
阅读更多...
【优质】「web开发网页制作」html+css+js导盲犬网页制作（5页面）

【优质】「web开发网页制作」html+css+js导盲犬网页制作（5页面）

导盲犬网页目录 涉及知识写在前面一、网页主题二、网页效果Page1、首页Page2、关于导盲犬Page3、阶段Page4、宣传视频Page5、登录 三、网页架构与技术3.1 脑海构思3.2 整体布局3.3 技术说明书 四、网页源码HtmlCSSJS 五、源码获取5.1 获取源码包 作者寄语 涉及知识 导盲犬介绍…
阅读更多...
flask_restful规范返回值之类型设置

flask_restful规范返回值之类型设置

大型的互联网项目中&#xff0c;返回的数据格式&#xff0c;有时是比较复杂的结构。 如&#xff1a;豆瓣电影 https://movie.douban.com/j/chart/top_list?type24&interval_id 100%3A90&action&start20&limit20 返回的值里有 json 或者列表数据&#xff0c…
阅读更多...
基于nodejs+vue家装一体化平台python-flask-django-php

基于nodejs+vue家装一体化平台python-flask-django-php

提高现下家装一体化平台的准确度&#xff0c;同时降低经济波动带来的不良影响&#xff0c;希望本文能对广大学者的研究提供参考。 前端技术&#xff1a;nodejsvueelementui, Express 框架于Node运行环境的Web框架, 语言 node.js 框架&#xff1a;Express 前端:Vue.js 数据库&am…
阅读更多...
Nodejs沙盒逃逸

Nodejs沙盒逃逸

Buffer 在较早一点的node.js版本中 (8.0 之前)&#xff0c;当 Buffer 的构造函数传入数字时, 会得到与数字长度一致的一个 Buffer&#xff0c;并且这个 Buffer 是未清零的。8.0 之后的版本可以通过另一个函数 Buffer.allocUnsafe(size) 来获得未清空的内存。 注&#xff1a;关…
阅读更多...
elasticsearch 8.12+kibana 8.12

elasticsearch 8.12+kibana 8.12

准备工作&#xff1a;1.下载相关的安装包放到/usr/local/ES下面 elasticsearch下载地址:Download Elasticsearch | Elastic elasticsearch-head-master下载地址:https://github.com/mobz/elasticsearch-head/archive/master.zip node下载地址:Index of /dist/ kibana地址:Downl…
阅读更多...
CSS及javascript

CSS及javascript

一、CSS简介 css是一门语言&#xff0c;用于控制网页的表现。 cascading style sheet:层叠样式表 二、css的导入方式 css代码与html代码的结合方式 &#xff08;1&#xff09;css导入html有三种方式&#xff1a; 1.内联样式&#xff1a;<div style"color:red&quo…
阅读更多...
C语言 | qsort（）函数使用

C语言 | qsort（）函数使用

目录&#xff1a; 1.qsort介绍 2.使⽤qsort函数 排序 整型数据 3.使⽤qsort函数 排序 结构体数据 4. qsort函数的模拟实现冒泡排序 qsort()函数 是一个 C语言编译器函数库自带的排序函数&#xff0c; 它可以对指定数组&#xff08;包括字符串&#xff0c;二维数组&#x…
阅读更多...
Qt与编码

Qt与编码

ASCII码:一个字节&#xff0c;256个字符。 Unicode:字母&#xff0c;汉字都占用两个字节。 utf-8:字母一个字节&#xff0c;汉字3个字节。 gbk:字母一个字节&#xff0c;汉字2个字节。 gb2312:可以表示汉字&#xff0c;gb2312<gbk。 编码查看&#xff1a; https://www.…
阅读更多...
sonar+gitlab提交阻断 增量扫描

sonar+gitlab提交阻断 增量扫描

通过本文&#xff0c;您将可以学习到 sonarqube、git\gitlab、shell、sonar-scanner、sonarlint 一、前言 sonarqube 是一款开源的静态代码扫描工具。 实际生产应用中&#xff0c;sonarqube 如何落地&#xff0c;需要考虑以下四个维度&#xff1a; 1、规则的来源 现在规则的…
阅读更多...
SQLite数据库成为内存中数据库（三）

SQLite数据库成为内存中数据库（三）

返回&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;SQLite 下一篇&#xff1a;未发表 ​​ SQLite数据库通常存储在单个普通磁盘中文件。但是&#xff0c;在某些情况下&#xff0c;数据库可能存储在内存。 强制SQLite数据库纯粹存在的最常见方法在内存中是使用特…
阅读更多...
【前端】代码案例

【前端】代码案例

1.猜数字 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>猜数字</title> </head> <…
阅读更多...
Redis锁，乐观锁与悲观锁

Redis锁，乐观锁与悲观锁

锁 悲观锁 认为什么时候都会出问题&#xff0c;无论做什么都会加锁 乐观锁 很乐观&#xff0c;认为什么时候都不会出问题&#xff0c;所以不会上锁。 更新数据时去判断一下&#xff0c;在此期间&#xff0c;是否有人修改过这个数据 应用于&#xff1a;秒杀场景 **watch*…
阅读更多...
【网络爬虫】(2) requests模块，案例：网络图片爬取，附Python代码

【网络爬虫】(2) requests模块，案例：网络图片爬取，附Python代码

1. 基本原理 1.1 requests 模块 requests 是 Python 中一个非常流行的 HTTP 客户端库&#xff0c;用于发送所有的 HTTP 请求类型。它基于 urllib&#xff0c;但比 urllib 更易用。 中文文档地址&#xff1a;Requests: 让 HTTP 服务人类 — Requests 2.18.1 文档 &#xff0…
阅读更多...
FTP 文件传输服务

FTP 文件传输服务

FTP连接 控制连接&#xff1a;TCP 21&#xff0c;用于发送FTP命令信息 数据连接&#xff1a;TCP 20&#xff0c;用于上传、下载数据 数据连接的建立类型&#xff1a; 主动模式&#xff1a;服务端从 20 端口主动向客户端发起连接 被动模式&#xff1a;服务端在指定范围…
阅读更多...
【Linux】 centos7安装卸载SQL server（2017、2019）

【Linux】 centos7安装卸载SQL server（2017、2019）

一、安装配置 准备一个基础Linux配置&#xff1a; 内存为20GB 运行内存为2GB的系统&#xff08;数据库小于2GB安装不了&#xff09; 1、网络配置 我们需要进行网络的连接 进入 cd /ect/sysconfig/network-script/ 编辑文件ifcfg-ens33 vi ifcfg-ens33 Insert键进行编辑 把ONBOO…
阅读更多...
flask_restful规范返回值

flask_restful规范返回值

使用方法 导入 flask_restful.marshal_with 装饰器 定义一个字典变量来指定需要返回的标准化字段&#xff0c;以及该字段的数据类型 在请求方法中&#xff0c;返回自定义对象的时候&#xff0c; flask_restful 会自动的读 取对象模型上的所有属性。 组装成一个符合标准化参…
阅读更多...
最新文章

Copyright @ 2022~2023