四数之和--力扣18

四数之和

  • 题目
  • 思路
  • 代码

题目

在这里插入图片描述

思路

类似于三数之和,先排序,利用双指针解题。

如果排序后的第一个元素大于目标值,直接返回,为什么nums[i]需要大于等于0,因为目标值可能为负数。比如:数组是[-4, -3, -2, -1],target是-10,不能因为-4 > -10而跳过。

四数之和的双指针解法是两层for循环nums[i] + nums[j]为确定值,依然是循环内有left和right下标作为双指针,找出nums[i] + nums[j] + nums[left] + nums[right] == target的情况

去重和三数之和一样很简单,i和j如果重复了怎么办,它们是nums里遍历的元素,那么应该直接跳过去。nums[i+ 1]是j,nums[j+1]是left,这些都是要去重的,所以我们考虑nums[i-1]和nums[j-1]。

left和right去重就很简单了,因为我们已经确定了前两个值,要想确定最终的目标值,如果left确定了,那么right就是固定的,所以left指针和left+1相等时,我们直接进行left++就可以了,同理,right类似。

代码

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {//返回二维数组vector<vector<int>> res;//排序,方便后续使用双指针sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); i++) {//如果排序后第一个元素大于目标值,直接返回,为什么需要大于等于0,因为目标值可能为负数if (nums[i] > target && nums[i] >= 0) {break;}//对i去重if (i > 0 && nums[i] == nums[i - 1]) continue;for (int j = i + 1; j < nums.size(); j++) {if (nums[i] + nums[j] > target && nums[i] >= 0) {break;}//对j去重 注意 j是从i+1开始的if (j > i + 1 && nums[j] == nums[j - 1]) continue;//开始双指针循环查找int left = j + 1;int right = nums.size() - 1;while (right > left) {if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) {right--;} else if ((long)nums[i] + nums[j] + nums[left] + nums[right] < target) {left++;} else {res.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});//对left和right去重while (right > left && nums[left] == nums[left + 1]) left++;while (right > left && nums[right] == nums[right - 1]) right--;//一轮循环完,双指针向内收缩right--;left++;}}}}return res;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大数据安全需求分析与安全保护工程

大数据安全威胁与需求分析 特征&#xff1a;海量是数据规模、快速的数据流转、多样的数据类型和价值密度低 种类和来源&#xff1a;结构化、半结构化和非结构化数据 数据种类&#xff1a; 结构化数据&#xff1a;关系模型数据&#xff0c;以关系数据库表形式管理的数据 非…

Docker:对已有的容器,对当前容器映射的端口实时 (增删改查)

首先我的docker已经起了一个容器&#xff0c;我突然想把他的80->80映射的端口改成80->8080 但是我不想去新启动容器&#xff0c;想在现有容器基础上去修改&#xff0c;或者我想删除某个端口映射&#xff08;只是大概思路&#xff09; 如何寻找容器配置文件位置 首先我这…

Linux系统使用Docker安装DockerUI并实现远程管理本地容器无需公网IP

文章目录 前言1. 安装部署DockerUI2. 安装cpolar内网穿透3. 配置DockerUI公网访问地址4. 公网远程访问DockerUI5. 固定DockerUI公网地址 前言 DockerUI是一个docker容器镜像的可视化图形化管理工具。DockerUI可以用来轻松构建、管理和维护docker环境。它是完全开源且免费的。基…

立足本土,面向全球 | 全视通闪耀亮相Medical Fair Asia新加坡医疗展

Medical Fair Asia是亚洲地区最大的医疗设备、医疗器械和医疗技术展览会之一&#xff0c;自1997年创办以来&#xff0c;每两年在新加坡举办一次。该展会不仅是新加坡医疗行业交流的龙头平台&#xff0c;也是亚洲乃至全球医疗企业和专业人士共聚一堂、展示最新产品和技术的重要舞…

红黑树的删除

文章目录 前言一.删除的节点左子树右子树都有二.删除的节点只有左/右子树删除调整操作 三.删除的节点没有孩子1.删除的节点为红色2.删除的节点为黑色1).兄弟节点为黑色(1).兄弟节点至少有一个红色的孩子节点LL型RR型RL型LR型 (2).兄弟节点没有孩子或所有孩子为黑色 2).兄弟节点…

vue3使用leaflet+trackplayer实现非地图动画轨迹(市场平面图动态轨迹)

vue3使用leaflettrackplayer实现非地图动画轨迹(市场平面图动态轨迹) 先下载 leaflet 和 leaflet-trackplayer两个主要库 leaflet官方文档 npm install leaflet npm install leaflet-trackplayer然后在页面中引用 html <template><button click"playMap&quo…

【时时三省】(C语言基础)指针进阶 例题7

山不在高&#xff0c;有仙则名。水不在深&#xff0c;有龙则灵。 ----CSDN 时时三省 二维数组 第一个a 因为它有12个元素 每个元素占4个字节 所以就打印48 第二个a&#xff3b;0&#xff3d;&#xff3b;0&#xff3d; 表示是第一行第一个元素 所…

滑动窗口算法—最小覆盖子串

题目 ”最小覆盖子串“问题&#xff0c;难度为Hard&#xff0c;题目如下&#xff1a; 给你两个字符串 S 和 T&#xff0c;请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串&#xff0c;则算法返回空串&#xff0c;如果存在这样一个子串&#xff0c;则可…

Codeforces practice C++ 2024/9/11 - 2024/9/13

D. Mathematical Problem Codeforces Round 954 (Div. 3) 原题链接&#xff1a;https://codeforces.com/contest/1986/problem/D 题目标签分类&#xff1a;brute force&#xff0c;dp&#xff0c;greedy&#xff0c;implementation&#xff0c;math&#xff0c;two pointers…

[数据集][目标检测]乱堆物料检测数据集VOC+YOLO格式1143张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;1143 标注数量(xml文件个数)&#xff1a;1143 标注数量(txt文件个数)&#xff1a;1143 标注…

Java高级Day41-反射入门

115.反射 反射机制 1.根据配置文件re.properties指定信息&#xff0c;创建Cat对象并调用hi方法 SuppressWarnings({"all"}) public class ReflectionQuestion {public static void main(String[] args) throws IOException {//根据配置文件 re.properties 指定信息…

交叉编译工具链的安装及带wiringPi库的交叉编译实现

交叉编译工具链的安装及带wiringPi库的交叉编译实现 交叉编译的概念交叉编译工具链的安装下载交叉编译工具链配置环境遍变量编译程序到ARM平台 带wiringPi库的交叉编译下载编译wiringPi库调用树莓派的wringPi库 交叉编译的概念 交叉编译是在一个平台上生成另一个平台上的可执行…

xshell密钥方式连接阿里云Linux

前提条件 有阿里云ECS linux实例安装好xshell工具 步骤 创建密钥对并绑定ECS实例 浏览器登录阿里云-->控制台-->ECS服务器-->网络与安全-->密钥对-->创建密钥对 根据提示填写密钥名称-->选中默认资源组-->创建 创建完成&#xff0c;会自动下载密钥对的…

WPF实现Hammer 3D入门学习

代码下载&#xff1a;https://download.csdn.net/download/bjhtgy/89748674

【Python】生成图片验证码

1. 首先安装第三方库PIL&#xff08;图像处理库&#xff09; pip install pillow 2. 编写生成验证码代码 这里字体 SimHei.ttf 文件要放在该文件目录下。 import random from PIL import Image, ImageDraw, ImageFont, ImageFilterdef check_code(width128, height30, char…

PowerShell install 一键部署Oracle21c-xe

Oracle21c-xe前言 无论您是开发人员、DBA、数据科学家、教育工作者,还是仅仅对数据库感兴趣,Oracle Database Express Edition (XE) 都是理想的入门方式。它是全球企业可依赖的强大的 Oracle Database,提供简单的下载、易于使用和功能齐全的体验。您可以在任何环境中使用该…

Redis:发布(pub)与订阅(sub)实战

前言 Redis发布订阅&#xff08;Pub/Sub&#xff09;是Redis提供的一种消息传递机制&#xff0c;它使用“发布者-订阅者”&#xff08;publisher-subscriber&#xff09;模式来处理消息传递。在这种模式下&#xff0c;发布者将消息发布到一组订阅者中&#xff0c;而无需关心谁…

基于MATLAB的图像融合设计

摘 要 图像融合能够将不同类型传感器获取的同一对象的图像数据进行空间配准。并且采用一定的算法将不同类型的传感器获取的同一对象的图像数据所含用的信息优势或互补性有机地结合起来产生的新的图像数据。这种新数据含有所研究对象的更多信息表征&#xff0c;与单一图像相对比…

learn C++ NO.13——list

前言 本文将从list的使用&#xff0c;再到根据sgi库对于list实现作为参考模拟实现一下list。通过模拟实现来增加对它的理解。 介绍list list是一个由带头双向循环链表实现的STL容器&#xff0c;它提供常规时间内对数据进行插入和删除操作。 list在内存中存储不连续的空间存储…

计算机组成原理(第二次笔记)

各种码 真值 (书写用)&#xff1a; 将用“”、“-” 表示正负的二进制数称为真值 机器不能识别书写格式&#xff0c;故用“0/1”表示“/-”符号。 机器码 (机器内部使用)&#xff1a; 将符号和数值一起编码表示的二进制数称为机器码。 常用机器码&#xff1a;原码、 反码、 补…