当前位置: 首页 > news >正文

【数据结构和算法】 K 和数对的最大数目

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 方法一:双指针排序

三、代码

3.1 方法一:双指针排序

3.2 方法二:两次遍历 hash 法

3.3 方法三:一次遍历 hash 法

四、复杂度分析

4.1 方法一:双指针排序

4.2 方法二:两次遍历 hash 法

4.3 方法三:一次遍历 hash 法


前言

这是力扣的 1679 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。


一、题目描述

给你一个整数数组 nums 和一个整数 k 。

每一步操作中,你需要从数组中选出和为 k 的两个整数,并将它们移出数组。

返回你可以对数组执行的最大操作数。

示例 1:

输入:nums = [1,2,3,4], k = 5
输出:2
解释:开始时 nums = [1,2,3,4]:
- 移出 1 和 4 ,之后 nums = [2,3]
- 移出 2 和 3 ,之后 nums = []
不再有和为 5 的数对,因此最多执行 2 次操作。

示例 2:

输入:nums = [3,1,3,4,3], k = 6
输出:1
解释:开始时 nums = [3,1,3,4,3]:
- 移出前两个 3 ,之后nums = [1,4,3]
不再有和为 6 的数对,因此最多执行 1 次操作。

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

二、题解

本题其实有很多种解法,比方说两次遍历 hash 法,一次遍历 hash 法,但这些方法都不如双指针排序法简洁干练,销量也没双指针排序法高。

两次遍历 hash 法:时间复杂度O(n),空间复杂度O(n)。

一次遍历 hash 法:时间复杂度O(n),空间复杂度O(n)。

双指针排序法:时间复杂度O(nlogn + n),空间复杂度O(1)。

但按理说排序的时间复杂度是大于 hash 的,但是他的代码效率反而更高,说明 hash 算法的效率太低,或者冲突严重。

在下面我也会贴两次遍历 hash 法和一次遍历 hash 法的代码,解题思路就不讲解了。

2.1 方法一:双指针排序

思路与算法:

1. 首先先将数组排序,在设定左右指针 i 和 j ,分别指向数组的头和尾。

2. 将两个指针指向的数进行求和:

  • 若和大于目标,则说明太大了,需要右指针左移(可以使和变小)。
  • 若和小于目标,则说明太小了,需要左指针右移(可以使和变大)。
  • 若和等于目标,则两个指针都往中间移动,结果 + 1 。

3. 循环2步骤直至左指针不在右指针的左边。


三、代码

3.1 方法一:双指针排序

Java版本:

class Solution {public int maxOperations(int[] nums, int k) {int count = 0, i = 0, j = nums.length - 1;Arrays.sort(nums);while (i < j) {if (nums[i] + nums[j] == k) {count++;i++;j--;} else if (nums[i] + nums[j] > k) {j--;} else {i++;}}return count;}
}

C++版本: 

#include <algorithm>
#include <vector>class Solution {
public:int maxOperations(std::vector<int>& nums, int k) {int count = 0;std::sort(nums.begin(), nums.end());int i = 0, j = nums.size() - 1;while (i < j) {if (nums[i] + nums[j] == k) {count++;i++;j--;} else if (nums[i] + nums[j] > k) {j--;} else {i++;}}return count;}
};

Python版本: 

class Solution:def maxOperations(self, nums: List[int], k: int) -> int:count = 0nums.sort()i, j = 0, len(nums) - 1while i < j:if nums[i] + nums[j] == k:count += 1i += 1j -= 1elif nums[i] + nums[j] > k:j -= 1else:i += 1return count

3.2 方法二:两次遍历 hash 法

Java版本:

class Solution {public int maxOperations(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>(nums.length);//统计每个数据出现的次数,key为数据,value为次数for (int num : nums) {Integer i = map.getOrDefault(num, 0);map.put(num, i + 1);}int result = 0;for (int num : nums) {// 求和达到K的数据int x = k - num;// 从map获取xint i = map.get(num);//如果次数小于等于0,说明数据被使用过了【就算后面遍历到他,也可以跳过了】if (i <= 0) {continue;}//统计数量减一,先减去,防止两个相同的数据相加达到K,而只有一个数据//【有个大兄弟有疑问,为什么直接删了。补充一下:因为是两遍循环,第一次就统计过所有的数据了,如果后面的if无法进入,那么之后也不可能了,删了就删了,无所谓了。】map.put(num, i - 1);// 是否有 另一个数据。且统计的数量大于0if (map.containsKey(x) && map.get(x) > 0) {result++;//结果+1map.put(x, map.get(x) - 1);// 数量减一}}return result;}
}

3.3 方法三:一次遍历 hash 法

Java版本:

class Solution {public int maxOperations(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>(nums.length);int result = 0;//统计每个数据出现的次数,key为数据,value为次数for (int num : nums) {// 获取求和的另一个数int x = k - num;// 从map获取xInteger i = map.get(x);// 是否有 另一个数据。且统计的数量大于0if (i != null && map.get(x) > 0) {result++;//结果+1map.put(x, map.get(x) - 1);// 数量减一continue;}//这个数没有被使用,统计数量+1Integer count = map.getOrDefault(num, 0);map.put(num, count + 1);}return result;}
}

四、复杂度分析

4.1 方法一:双指针排序

  • 时间复杂度O(nlogn + n)。
  • 空间复杂度O(1)。

4.2 方法二:两次遍历 hash 法

  • 时间复杂度O(n)。
  • 空间复杂度O(n)。

4.3 方法三:一次遍历 hash 法

  • 时间复杂度O(n)。
  • 空间复杂度O(n)。

相关文章:

【数据结构和算法】 K 和数对的最大数目

其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 方法一&#xff1a;双指针排序 三、代码 3.1 方法一&#xff1a;双指针排序 3.2 方法二&#xff1…...

基于ssm高校推免报名系统源码和论文

网络的广泛应用给生活带来了十分的便利。所以把高校推免报名管理与现在网络相结合&#xff0c;利用java技术建设高校推免报名管理系统&#xff0c;实现高校推免报名的信息化。则对于进一步提高高校推免报名管理发展&#xff0c;丰富高校推免报名管理经验能起到不少的促进作用。…...

算法设计与分析2023秋-头歌实验-实验七 动态规划

文章目录 第1关&#xff1a;数塔问题任务描述相关知识编程要求解题思路测试说明参考答案 第2关&#xff1a;最长公共子序列任务描述相关知识编程要求解题思路&#xff1a;测试说明参考答案 第3关&#xff1a;求序列-2 11 -4 13 -5 -2的最大子段和任务描述相关知识编程要求解题思…...

复杂 SQL 实现分组分情况分页查询

其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、根据 camp_status 字段分为 6 种情况 1.1 SQL语句 1.2 SQL解释 二、分页 SQL 实现 2.1 SQL语句 2.2 根据 camp_type 区分返…...

JavaScript---如何完美的判断返回对象是否有值

如何判断一个对象为空是我们在开发中经常会遇到的问题&#xff0c;今天我们来聊聊几种经常使用的方法&#xff0c;以及在不同的场景下我们如何去使用。 1. JSON.stringify JSON.stringify 方法可以使对象序列化&#xff0c;转为相应的 JSON 格式。 js 复制代码 const obj {…...

kafka offset sasl加密连接

kafka-tool&#xff08;offset&#xff09; 进行SCRAM连接&#xff0c;直接上图 填写jaas的认证&#xff08;账密 引用包&#xff09;...

Android studio矩形背景颜色以及弧度的设置

在这里插入图片描述 Android的shape中主要设置的属性 corners&#xff1a;用于设置形状的圆角&#xff0c;可以设置圆角的半径、颜色等属性。 stroke&#xff1a;用于设置形状的边框&#xff0c;可以设置边框的宽度、颜色等属性。 padding&#xff1a;用于设置形状的内边距&…...

Acrel-1000DP分布式光伏系统在某重工企业18MW分布式光伏中应用——安科瑞 顾烊宇

摘 要&#xff1a;分布式光伏发电特指在用户场地附近建设&#xff0c;运行方式以用户侧自发自用、余电上网&#xff0c;且在配电系统平衡调节为特征的光伏发电设施&#xff0c;是一种新型的、具有广阔发展前景的发电和能源综合利用方式&#xff0c;它倡导就近发电&#xff0c;就…...

3 python基本语法 - Dict 字典

Python 中字典&#xff08;dict&#xff09;是一种无序的、可变的序列&#xff0c;它的元素以“键值对&#xff08;key-value&#xff09;”的形式存储。相对地&#xff0c;列表&#xff08;list&#xff09;和元组&#xff08;tuple&#xff09;都是有序的序列&#xff0c;它们…...

Magnific AI:彻底改变 AI 生成图像的升级

在我最近与 Magnific AI 的讨论中&#xff0c;我不仅感到惊讶&#xff0c;而且对该工具提供的质量和可能性着迷。我发现 Magnific AI 能够转换人工智能生成的图像&#xff08;这些图像通常只能以低分辨率提供&#xff09;&#xff0c;尤其令人印象深刻&#xff0c;不仅在可打印…...

BKP 备份寄存器 RTC 实时时钟-stm32入门

这一章节我们要讲的主要内容是 RTC 实时时钟&#xff0c;对应手册&#xff0c;是第 16 章的位置。 实时时钟这个东西&#xff0c;本质上是一个定时器&#xff0c;但是这个定时器&#xff0c;是专门用来产生年月日时分秒&#xff0c;这种日期和时间信息的。所以学会了 STM32 的…...

1.1 数据结构-数据的表示

文章目录 1.1.1 二元关系及其性质:1.1.1.1 笛卡尔积:1.1.1.2 二元关系:持续更新当中 ....... 1.1.1 二元关系及其性质: 数据的基本单元称为额数据元素,数据是从客观事物的观测中的到的,数据元素并不是鼓励存在的,而是存在密切的联系,也因此才能表示和描述客观事物,数据元素之间…...

UNIX Linux系统 启动PPOCRLabel报错[已放弃 (核心已转储)]

参照官方教程安装后&#xff0c;启动PPOCRLabel报错&#xff1a;[已放弃 (核心已转储)] 官方链接地址&#xff1a;PPOCRLabelv2 $~ PPOCRLabel --lang ch QObject::moveToThread: Current thread (0x561534309430) is not the objects thread (0x56153929eac0). Cannot move to…...

前端开发中的webpack打包工具

前端技术发展迅猛&#xff0c;各种可以提高开发效率的新思想和框架层出不穷&#xff0c;但是它们都有一个共同点&#xff0c;即源代码无法直接运行&#xff0c;必须通过转换后才可以正常运行。webpack是目前主流的打包模块化JavaScript的工具之一。 本章主要涉及的知识点有&am…...

Mybatis配置-数据库厂商标识(databaseIdProvider)

MyBatis可以根据数据库供应商执行不同的语句。多数据库供应商支持是基于映射语句的databaseId属性。MyBatis将加载所有没有databaseId属性或具有与当前数据库匹配的databaseId属性的语句。如果找到具有和不具有databaseId的相同语句&#xff0c;则后者将被丢弃。要启用多供应商…...

【Java】使用递归的方法获取层级关系数据demo

使用递归来完善各种业务数据的层级关系的获取 引言&#xff1a;在Java开发中&#xff0c;我们通常会遇到层层递进的关系型数据的获取问题&#xff0c;有时是树状解构&#xff0c;或金字塔结构&#xff0c;怎么描述都行&#xff0c;错综复杂的关系在程序中还是可以理清的。 这…...

工业6轴机械臂运动学逆解(解析解)

工业6轴机械臂运动学逆解&#xff08;解析解&#xff09; 通常工业机械臂采用6旋转轴串连的形式&#xff0c;保证了灵活性&#xff0c;但为其运动学逆解&#xff08;即已知机械臂末端的位姿 P P P&#xff0c;求机械臂各个旋转轴的旋转角&#xff09;带来了较大的困难&#xff…...

管理类联考——数学——真题篇——按题型分类——充分性判断题——蒙猜A/B

老规矩&#xff0c;看目录&#xff0c;平均3-5题 文章目录 A/B2023真题&#xff08;2023-19&#xff09;-A-选项特点&#xff1a;两个等号&#xff1b;-判断需联立的难易&#xff1a;难&#xff0c;看着感觉需要联立&#xff0c;所以判断联立需要有理论支撑&#xff0c;不然还…...

为什么GRU和LSTM能够缓解梯度消失或梯度爆炸问题?

1、什么是梯度消失&#xff08;gradient vanishing&#xff09;&#xff1f; 参数更新过小&#xff0c;在每次更新时几乎不会移动&#xff0c;导致模型无法学习。 2、什么是梯度爆炸&#xff08;gradient exploding&#xff09;&#xff1f; 参数更新过小大&#xff0c;破坏了…...

【力扣100】146.LRU缓存

添加链接描述 class DLinkedNode:def __init__(self, key0, value0):self.key keyself.value valueself.prev Noneself.next Noneclass LRUCache:def __init__(self, capacity: int):self.cache dict()# 使用伪头部和伪尾部节点 self.head DLinkedNode()self.tail D…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...