【数据结构和算法】 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 <= 1051 <= nums[i] <= 1091 <= 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 方法一:双指针排序 三、代码 3.1 方法一:双指针排序 3.2 方法二࿱…...
基于ssm高校推免报名系统源码和论文
网络的广泛应用给生活带来了十分的便利。所以把高校推免报名管理与现在网络相结合,利用java技术建设高校推免报名管理系统,实现高校推免报名的信息化。则对于进一步提高高校推免报名管理发展,丰富高校推免报名管理经验能起到不少的促进作用。…...
算法设计与分析2023秋-头歌实验-实验七 动态规划
文章目录 第1关:数塔问题任务描述相关知识编程要求解题思路测试说明参考答案 第2关:最长公共子序列任务描述相关知识编程要求解题思路:测试说明参考答案 第3关:求序列-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---如何完美的判断返回对象是否有值
如何判断一个对象为空是我们在开发中经常会遇到的问题,今天我们来聊聊几种经常使用的方法,以及在不同的场景下我们如何去使用。 1. JSON.stringify JSON.stringify 方法可以使对象序列化,转为相应的 JSON 格式。 js 复制代码 const obj {…...
kafka offset sasl加密连接
kafka-tool(offset) 进行SCRAM连接,直接上图 填写jaas的认证(账密 引用包)...
Android studio矩形背景颜色以及弧度的设置
在这里插入图片描述 Android的shape中主要设置的属性 corners:用于设置形状的圆角,可以设置圆角的半径、颜色等属性。 stroke:用于设置形状的边框,可以设置边框的宽度、颜色等属性。 padding:用于设置形状的内边距&…...
Acrel-1000DP分布式光伏系统在某重工企业18MW分布式光伏中应用——安科瑞 顾烊宇
摘 要:分布式光伏发电特指在用户场地附近建设,运行方式以用户侧自发自用、余电上网,且在配电系统平衡调节为特征的光伏发电设施,是一种新型的、具有广阔发展前景的发电和能源综合利用方式,它倡导就近发电,就…...
3 python基本语法 - Dict 字典
Python 中字典(dict)是一种无序的、可变的序列,它的元素以“键值对(key-value)”的形式存储。相对地,列表(list)和元组(tuple)都是有序的序列,它们…...
Magnific AI:彻底改变 AI 生成图像的升级
在我最近与 Magnific AI 的讨论中,我不仅感到惊讶,而且对该工具提供的质量和可能性着迷。我发现 Magnific AI 能够转换人工智能生成的图像(这些图像通常只能以低分辨率提供),尤其令人印象深刻,不仅在可打印…...
BKP 备份寄存器 RTC 实时时钟-stm32入门
这一章节我们要讲的主要内容是 RTC 实时时钟,对应手册,是第 16 章的位置。 实时时钟这个东西,本质上是一个定时器,但是这个定时器,是专门用来产生年月日时分秒,这种日期和时间信息的。所以学会了 STM32 的…...
1.1 数据结构-数据的表示
文章目录 1.1.1 二元关系及其性质:1.1.1.1 笛卡尔积:1.1.1.2 二元关系:持续更新当中 ....... 1.1.1 二元关系及其性质: 数据的基本单元称为额数据元素,数据是从客观事物的观测中的到的,数据元素并不是鼓励存在的,而是存在密切的联系,也因此才能表示和描述客观事物,数据元素之间…...
UNIX Linux系统 启动PPOCRLabel报错[已放弃 (核心已转储)]
参照官方教程安装后,启动PPOCRLabel报错:[已放弃 (核心已转储)] 官方链接地址:PPOCRLabelv2 $~ PPOCRLabel --lang ch QObject::moveToThread: Current thread (0x561534309430) is not the objects thread (0x56153929eac0). Cannot move to…...
前端开发中的webpack打包工具
前端技术发展迅猛,各种可以提高开发效率的新思想和框架层出不穷,但是它们都有一个共同点,即源代码无法直接运行,必须通过转换后才可以正常运行。webpack是目前主流的打包模块化JavaScript的工具之一。 本章主要涉及的知识点有&am…...
Mybatis配置-数据库厂商标识(databaseIdProvider)
MyBatis可以根据数据库供应商执行不同的语句。多数据库供应商支持是基于映射语句的databaseId属性。MyBatis将加载所有没有databaseId属性或具有与当前数据库匹配的databaseId属性的语句。如果找到具有和不具有databaseId的相同语句,则后者将被丢弃。要启用多供应商…...
【Java】使用递归的方法获取层级关系数据demo
使用递归来完善各种业务数据的层级关系的获取 引言:在Java开发中,我们通常会遇到层层递进的关系型数据的获取问题,有时是树状解构,或金字塔结构,怎么描述都行,错综复杂的关系在程序中还是可以理清的。 这…...
工业6轴机械臂运动学逆解(解析解)
工业6轴机械臂运动学逆解(解析解) 通常工业机械臂采用6旋转轴串连的形式,保证了灵活性,但为其运动学逆解(即已知机械臂末端的位姿 P P P,求机械臂各个旋转轴的旋转角)带来了较大的困难ÿ…...
管理类联考——数学——真题篇——按题型分类——充分性判断题——蒙猜A/B
老规矩,看目录,平均3-5题 文章目录 A/B2023真题(2023-19)-A-选项特点:两个等号;-判断需联立的难易:难,看着感觉需要联立,所以判断联立需要有理论支撑,不然还…...
为什么GRU和LSTM能够缓解梯度消失或梯度爆炸问题?
1、什么是梯度消失(gradient vanishing)? 参数更新过小,在每次更新时几乎不会移动,导致模型无法学习。 2、什么是梯度爆炸(gradient exploding)? 参数更新过小大,破坏了…...
【力扣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…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
