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

2023-12-19

其他系列文章导航

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 = 0
        nums.sort()
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == k:
                count += 1
                i += 1
                j -= 1
            elif nums[i] + nums[j] > k:
                j -= 1
            else:
                i += 1
        return 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获取x
            int i = map.get(num);
            //如果次数小于等于0,说明数据被使用过了【就算后面遍历到他,也可以跳过了】
            if (i <= 0) {
                continue;
            }
            //统计数量减一,先减去,防止两个相同的数据相加达到K,而只有一个数据
            //【有个大兄弟有疑问,为什么直接删了。补充一下:因为是两遍循环,第一次就统计过所有的数据了,如果后面的if无法进入,那么之后也不可能了,删了就删了,无所谓了。】
            map.put(num, i - 1);
            // 是否有 另一个数据。且统计的数量大于0
            if (map.containsKey(x) && map.get(x) > 0) {
                result++;//结果+1
                map.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获取x
            Integer i = map.get(x);
            // 是否有 另一个数据。且统计的数量大于0
            if (i != null && map.get(x) > 0) {
                result++;//结果+1
                map.put(x, map.get(x) - 1);// 数量减一
                continue;
            }
            //这个数没有被使用,统计数量+1
            Integer 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)。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

【数据结构和算法】 K 和数对的最大数目 的相关文章

  • Redis 块推送直到列表有空位

    我正在寻找类似的东西BLPUSH该命令将阻塞 直到列表的长度低于指定值max size 目的是防止生产者运行速度快于消费者时列表无限增长 功能与 python 非常相似Queue put https docs python org 3 li
  • 如何使用Spring Cache处理redis异常?

    我目前正在开发一个包含 Spring Data Redis 和 Spring Cache 的项目 在spring data redis中 我使用redis模板调用redis 我在 try catch 块中处理 redis 模板抛出的所有异常
  • Redis键空间事件不触发

    我有两个 Redis 客户端 在一个文件中我有一个简单的脚本设置并删除了 Redis 键 var redis require redis var client redis createClient 6379 127 0 0 1 client
  • 如何设置 Celery 以通过 ssl 与 Azure Redis 实例对话

    使用 的伟大答案 如何在microsoft azure上的django项目中配置celery redis https stackoverflow com questions 39616701 how to configure celery
  • Redis 排序集和解决关系

    我正在使用 Redis 排序集来存储我正在处理的项目的排名 我们没有预料到 我们想要如何处理关系 Redis 按字典顺序对具有相同分数的条目进行排序 但我们想要做的是对具有相同分数的所有条目给予相同的排名 例如在以下情况 redis 127
  • 如何批量删除Redis中数十万个带有特殊字符的key

    我们有一个包含数十万个 Redis 键的列表 其中包含各种特殊字符 我们希望批量删除它们 对于这个问题上的类似问题 有一些很好的答案 如何使用 Redis 自动删除与模式匹配的键 https stackoverflow com questi
  • socket.io 广播功能 & Redis pub/sub 架构

    如果有人能帮助我解决一个小疑问 我将不胜感激 使用socket io广播功能和在Redis上使用pub sub设计架构有什么区别 例如 在另一个示例中 node js 服务器正在侦听 socket io 针对 键 模型 todo 和值 数据
  • 有没有办法在 ruby​​ 中重新定义 []=+

    我正在尝试编写一个简单的 DSL 针对 Redis 并且我想自己定义 I have def key val redis zadd name val key end 我想定义 def key val redis zincrby name va
  • 为什么 Redis TimeSeries 不捕获聚合中的最后一个元素?

    我试图了解 Redis 的时间序列规则创建的工作原理 但我很困惑为什么 Redis 会忽略聚合中的最后一项 并想知道这是否是预期的行为 我在中创建了示例代码redis cli为了显示 127 0 0 1 6379 gt FLUSHALL O
  • 2 个具有共享 Redis 依赖的 Helm Chart

    目前 我有 2 个 Helm Charts Chart A 和 Chart B Chart A 和 Chart B 对 Redis 实例具有相同的依赖关系 如Chart yaml file dependencies name redis v
  • Laravel 所有会话 ID 与 Redis 驱动程序

    在我的应用程序中 我希望允许某些用户能够注销除他 她之外的所有其他用户 当会话驱动程序设置为文件时 我已经完成了此功能 但现在我使用 redis 作为会话驱动程序 并且我无法找到任何方法来列出所有当前会话 就像我在文件时所做的那样司机 问题
  • redis - 使用哈希

    我正在使用 redis 为我的 Web 应用程序实现社交流和通知系统 我是 redis 的新手 我对哈希值及其效率有一些疑问 我读过这篇很棒的文章Instagram 帖子 http instagram engineering tumblr
  • 有没有办法让特定的key在集群模式下定位到特定的redis实例上?

    我想让我的多锁位于不同的redis实例上 我发现redission可以指定一个实例来执行命令 但是如果该命令与key相关 则指定的实例会将命令传输到另一个实例 你能给我一些建议吗 你可以 但这并不是微不足道的 首先 Redis 在键中使用大
  • 如何使redis中的“HSET”子键“过期”?

    我需要使 Redis 哈希中所有超过 1 个月的密钥过期 这不可能 https github com antirez redis issues 167 issuecomment 2559040 为了保持 Redis 简单 https git
  • 为什么Redis中没有有序的hashmap?

    Redis 数据类型 http redis io topics data types包括排序集 http redis io topics data types intro sorted sets以及其他用于键值存储的必要数据结构 但我想知道
  • Redis+Docker+Django - 错误 111 连接被拒绝

    我正在尝试使用 Redis 作为使用 Docker Compose 的 Django 项目的 Celery 代理 我无法弄清楚我到底做错了什么 但尽管控制台日志消息告诉我 Redis 正在运行并接受连接 事实上 当我这样做时 docker
  • 使用redis进行树形数据结构

    我需要为基于树的键值开发一个缓存系统 与Windows注册表编辑器非常相似 其中缓存键是字符串 表示树中到值的路径 可以是原始类型 int string bool double 等 或子树本身 例如 key root x y z w val
  • Redis 队列工作程序在 utcparse 中崩溃

    我正在尝试按照以下教程获得基本的 rq 工作 https blog miguelgrinberg com post the flask mega tutorial part xxii background jobs https blog m
  • docker-compose:容器之间的 Redis 连接被拒绝

    我正在尝试设置一个 docker compose 文件 该文件旨在替换运行多个进程 RQ 工作线程 RQ 仪表板和 Flask 应用程序 的单个 Docker 容器解决方案导师 http supervisord org 主机系统是 Debi
  • 如何延长 django-redis 中的缓存 ttl(生存时间)?

    我正在使用 django 1 5 4 和 django redis 3 7 1 我想延长缓存的 ttl 生存时间 当我取回它时 这是示例代码 from django core cache import cache foo cache get

随机推荐

  • CNP日志采集组件使用说明

    移动云CNP上线了日志采集组件 整体功能类似ELK 可以实现集群容器日志的数据采集 汇聚 统一检索等功能 使用也很简单 首先安装组件 然后配置采集规则 目前支持标准输出和日志文件两种采集方案 标准输出很好理解 只需要你把日式输出到控制台 这
  • json转换工具属性排序

    json 对象属性的输出顺序测试 fastJson 有序 jackson gson无序 需代码中人工按约定来编码 接口数据签名规则 fastJson会根据对象的字段的首字母来排序 而jackson gson是根据对象的类中定义的属性的代码中
  • 工业5G路由器助力AGV工厂建设,确保自动流水线高效运转

    随着制造业自动化 智能化转型升级的需求 山东省济南市一家汽车零部件生产企业计划建设全自动生产流水线 并使用AGV替代部分人工运输 以降本提效 但是对无线通信要求极高的AGV系统在复杂的工厂建筑内很难获得稳定的信号覆盖 AGV之间 与控制中心
  • Redis 的键管理

    一 Redis 数据库管理 Redis 是一个键值对 key value pair 的数据库服务器 其数据保存在 src server h redisDb 中 网上很多帖子说在 redis h 文件中 但是 redis 6 x版本目录中都没
  • HONEYWELL 05701-A-0361 离散输入/输出模块

    HONEYWELL 05701 A 0361 离散输入 输出模块 HONEYWELL 05701 A 0361 离散输入 输出模块产品详情 HONEYWELL 05701 A 0361 离散输入 输出模块通常用于工业自动化系统中 用于处理数
  • BENTLY 125680-01 位移检测模块

    BENTLY 125680 01 位移检测模块 BENTLY 125680 01 位移检测模块产品详情 Bently 125680 01 是一款位移检测模块 通常用于监测和测量工业设备的位移或振动 Bently Nevada是一家以提供振动
  • 【老生谈算法】matlab实现基于粒子群算法的PID控制器优化设计——粒子群算法

    Matlab实现基于粒子群算法的PID控制器优化设计 1 文档下载 本算法已经整理成文档如下 有需要的朋友可以点击进行下载 说明 文档 点击下载 本算法文档 老生谈算法 matlab实现基于粒子群算法的PID控制器优化设计 doc 更多ma
  • android 将服务设置为前台服务

    NotificationChannel channel new NotificationChannel id com xxx xx XxxService NotificationManager IMPORTANCE NONE channel
  • 【LeetCode刷题笔记】位运算

    231 2 的幂 解题思路 1 除法 不断循环判断 如果能被 2 整除 就不断除以 2 直到不能被 2 整除为止 最后结果如果是 1
  • HONEYWELL 05701-A-0511 框架模块

    HONEYWELL 05701 A 0511 框架模块 HONEYWELL 05701 A 0511 框架模块 产品详情 框架模块通常是一种用于构建更大型 更复杂系统的组件 在自动化和控制系统中 框架模块可能用于提供某些基础结构或功能 以支
  • 德思特EMC RICI测试方案助您对抗电磁设备干扰!

    来源 德思特测试测量 德思特方案丨德思特EMC RICI测试方案助您对抗电磁设备干扰 原文链接 https mp weixin qq com s D8wdQr reaFG yppT8nzkw 欢迎关注虹科 为您提供最新资讯 方案背景 电磁或
  • 企业电子招标采购系统源码Spring Cloud + Spring Boot + 前后端分离 + 二次开发

    项目说明 随着公司的快速发展 企业人员和经营规模不断壮大 公司对内部招采管理的提升提出了更高的要求 在企业里建立一个公平 公开 公正的采购环境 最大限度控制采购成本至关重要 符合国家电子招投标法律法规及相关规范 以及审计监督要求 通过电子化
  • 消息队列选型:Kafka 如何实现高性能?

    在分布式消息模块中 我将对消息队列中应用最广泛的 Kafka 和 RocketMQ 进行梳理 以便于你在应用中可以更好地进行消息队列选型 另外 这两款消息队列也是面试的高频考点 所以 本文我们就一起来看一下 Kafka 是如何实现高性能的
  • 【开题报告】基于SpringBoot的幼儿园学生成长管理系统的设计与实现

    1 研究背景 随着社会的发展和人们教育观念的转变 幼儿园在孩子的成长过程中扮演着越来越重要的角色 幼儿园是孩子们接受早期教育的重要阶段 对于他们的身心发展 学习能力和社交能力的培养起着至关重要的作用 因此 建立一套科学 高效的幼儿园学生成长
  • 边缘计算:构建下一代计算基础设施的关键技术

    随着物联网 人工智能和大数据等技术的快速发展 对计算基础设施的需求越来越高 然而 传统的云计算模式存在延迟高 数据传输量大等问题 为了解决这些问题 边缘计算应运而生 本文将介绍边缘计算的概念 探讨其在构建下一代计算基础设施中的关键技术 什么
  • BENTLY 125720-01 后卡模块

    BENTLY 125720 01 后卡模块 BENTLY 125720 01 后卡模块 产品详情 Bently Nevada 的产品 尤其是振动监测和机械振动解决方案 具有以下可能的特点 高精度测量 Bently Nevada 的产品通常设
  • 做一个wiki页面是体验HTML语义的好方法

    HTML语义 如何运用语义类标签来呈现Wiki网页 在上一篇文章中 我花了大量的篇幅和你解释了正确使用语义类标签的好处和一些场景 那么 哪些场景适合用到语义类标签呢 又如何运用语义类标签呢 不知道你还记不记得在大学时代 你被导师逼着改毕业论
  • git commit提交代码时 提交类别 - 提交开头命名规范

    feat 新功能 feature fix 修补bug refactor 重构 即不是新增功能 也不是修改bug的其他代码改动 style 格式 不影响代码运行的变动 test 增加测试 docs 文档 documentation chore
  • 20231219_101701 java io演练 功能演练 保存学生姓名到记事本

    需求 程序启动后 向用户询问学生姓名 如果输入的内容是s 就保存并退出 当程序结束后 把所有的输入的学生姓名 保存到名为students txt的记事本中 一个学生的名字占一行 分析 因为接收的是中文名字 所以建议使用字符流 我们随意选择一
  • 【数据结构和算法】 K 和数对的最大数目

    其他系列文章导航 Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一 题目描述 二 题解 2 1 方法一 双指针排序 三 代码 3 1 方法一 双指针排序 3