[python 刷题] 167 Two Sum II - Input Array Is Sorted 15 3Sum

[python 刷题] 167 Two Sum II - Input Array Is Sorted & 15 3Sum

虽然 3 sum 出来的比较早,不过按照解法来说,2 sum II 算是 3 sum 的前置解法

167 Two Sum II - Input Array Is Sorted

题目:

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

2Sum II 的前置肯定就是 2 Sum 了,不过这题比较难的地方在于空间复杂度只能为 O ( 1 ) O(1) O(1),也就是说,不能用额外的 dict 去存储补数

这题的解法就是双指针:

在这里插入图片描述

想像一下左右各有一个指针,如果想要两数之和变大,那么左边的指针可以向右移动。如果想要两数之和变小,那么右边的指针可以向左移动

在数组中没有解的情况下,一旦双指针相遇,这个循环就可以结束了,因此最差情况下就是遍历整个数组,所以时间复杂度为 O ( n ) O(n) O(n)。只需要保留两个指针,空间复杂度为 O ( 1 ) O(1) O(1)

解法如下:

class Solution:def twoSum(self, numbers: List[int], target: int) -> List[int]:l, r = 0, len(numbers) - 1while l < r:if numbers[l] + numbers[r] == target:return [l + 1, r + 1]if numbers[l] + numbers[r] < target:l += 1else:r -= 1

15 3Sum

题目:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

其实这题可以理解成一个嵌套版本的 2sum,因此先决条件就是进行一下排序。以题目中给的案例 [-1,0,1,2,-1,-4] 来说,排序完的结果为:[-4, -1, -1, 0, 1, 2],这个情况下,就可以把 3 sum 拆解成 2 sum II。

即 target 为 nums[i],找出 nums[j] + nums[k] = -nums[i] 的搭配,图解的话,大概就是这么理解的:

在这里插入图片描述

代码如下:

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res = collections.defaultdict(set)nums.sort()i = 0while i < len(nums) - 2:val = nums[i]j, k = i + 1, len(nums) - 1while j < k:if nums[j] + nums[k] + val == 0:res[val].add((nums[j], nums[k]))j += 1if nums[j] + nums[k] + val > 0:k -= 1else:j += 1i += 1return [[key, x, y] for key, val in res.items() for x, y in val]

空间复杂度为 O ( n ) O(n) O(n),首先排序有可能会创建一个新的数组,其次这里的确用了额外的 dict 去保存 tuple 的 set(为了不重复)

时间复杂度是 O ( n 2 ) O(n^2) O(n2),虽然排序是 O ( n l o g ( n ) ) O(n log(n)) O(nlog(n)) 的复杂度,不过下面两个循环爆了排序,成了 dominant factor

返回值用了 python 的 list comprehension 技巧,是一个可以把两个循环压缩成一行,并且生成 list 的方法。python 内部对 list comprehension 的实现有优化,一般来说 list comprehension 的效率比循环快

这行代码解析起来就是:

  • 从 res.items() 中获取 key(数字), val(tuple) 的 k-v 对
  • 从 tuple 中获取 x 和 y(对应的下标)
  • 遍历将将 key, x, y 组成一个数组,形成一个数组的数组

这是没做什么优化的解,不过另一个优化的方式如下:

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res = []nums.sort()for i, a in enumerate(nums):# Skip positive integersif a > 0:breakif i > 0 and a == nums[i - 1]:continuel, r = i + 1, len(nums) - 1while l < r:threeSum = a + nums[l] + nums[r]if threeSum > 0:r -= 1elif threeSum < 0:l += 1else:res.append([a, nums[l], nums[r]])l += 1r -= 1while nums[l] == nums[l - 1] and l < r:l += 1return res
  • enumerate() 会提供给数组的下标和当前值

    当前值为 nums[i]

  • 当 nums[i]>0 时,终止循环

    这是一个小优化,题目的需求本来就是 nums[i] + nums[j] + nums[k] == 0,这里的数组又进行了排序,当 nums[i]>0 时,nums[j] 和 nums[k] 必然也 >0

  • if i > 0 and a == nums[i - 1]: 这里去除重复值

    对比未被优化的代码,也就是跳过 nums[i] 已经作为 key 在 dict 的情况

  • l & r 的双指针实现一致

  • 最后的 while 也是另一个优化

    也是去除 tuple 中可能会出现重复值的方法,如:[1,1,1,2,2],这里会出现的所有 combo 为 (1, 1), (1, 2), (2, 2)

    如果 target 是 2,那么右边的指针就会一直减少,一直到指向的区域只有 1,并且获取第一个解

    这个时候只要维持右边的指针不动,左边在指针重复的情况下一直向右移动,那么当遇到 l==r 的情况下,循环也会终止

    所以这里只需要移动一边就行了

总体的时间和空间复杂度依旧维持不变,不过一些小的优化也能够提速不少

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

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

相关文章

Python中TensorFlow的长短期记忆神经网络(LSTM)、指数移动平均法预测股票市场和可视化...

原文链接&#xff1a;http://tecdat.cn/?p23689 本文探索Python中的长短期记忆&#xff08;LSTM&#xff09;网络&#xff0c;以及如何使用它们来进行股市预测&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 相关视频 在本文中&#xff0c;你将看到如何使用…

使用 FHE 实现加密大语言模型

近来&#xff0c;大语言模型 (LLM) 已被证明是提高编程、内容生成、文本分析、网络搜索及远程学习等诸多领域生产力的可靠工具。 大语言模型对用户隐私的影响 尽管 LLM 很有吸引力&#xff0c;但如何保护好 输入给这些模型的用户查询中的隐私 这一问题仍然存在。一方面&#xf…

【计算机网络】图解路由器(一)

图解路由器&#xff08;一&#xff09; 1、什么是路由器&#xff1f;2、什么是路由选择&#xff1f;3、什么是转发&#xff1f;4、路由器设备有哪些类型&#xff1f;5、根据性能分类&#xff0c;路由器有哪些类型&#xff1f;5.1 高端路由器5.2 中端路由器5.3 低端路由器 6、什…

Linux 安装 git

一 . 安装git 方式1&#xff1a;通过yum 安装 yum -y install git查看是否安装成功 git --version安装目录在&#xff1a;/usr/libexec/git-core yum 安装有一些缺点 &#xff1a;不能自己指定安装目录、安装版本 方式 2 下载tar.gz 包 配置 查看git 版本&#xff1a;Index…

电子器件系列57:肖特基二极管(BAS7005)

什么是肖特基二极管&#xff1f;肖特基二极管工作原理详解&#xff0c;几分钟带你搞定 - 知乎 这几个参数都是二极管很常见的参数&#xff1a;基本上就是正向导通时的极限电流电压&#xff0c;反向截止时的极限电流电压。功耗、温度、结电容&#xff0c;差不多就这些&#xff0…

WebGL HUD(平视显示器)

目录 HUD&#xff08;平视显示器&#xff09; 如何实现HUD 示例程序&#xff08;HUD.html&#xff09; 示例程序&#xff08;HUD.js&#xff09; 代码详解 在网页文字上方显示三维物体 代码详解 HUD&#xff08;平视显示器&#xff09; 平视显示器&#xff08;head…

Postman 的使用教程(详细)

Postman 使用教程 1. 是什么 Postman 是一个接口测试工具软件&#xff0c;可以帮助开发人员管理测试接口。 官网&#xff1a;https://www.getpostman.com/ 2. 安装 建议通过官网下载安装&#xff0c;不要去那些乱七八糟的下载平台&#xff0c;或者留言获取 官网下载地址&am…

package中添加一条命令,用来自动选择包管理器进行依赖安装

package中添加一条命令,用来自动选择包管理器进行依赖安装 前提: 当前项目为vite项目,所以直接使用import导入模块 package.json中的scripts添加 "scripts": {"start": "node scripts/init.js"...},文件目录为 init.js的文件为 import { e…

antd-design-vue Table组件全局配置(分页器...)

描述&#xff1a;该框架许多默认配置好像还不支持&#xff0c;一般都是挨个使用挨个配置。我的项目中也遇到了类似的情况&#xff0c;但是当需求发生变化时&#xff0c;代码所有的组件使用则都需要修改&#xff0c;这种方式真的很不礼貌。 《我为了一口醋包了顿饺子》 需求是将…

Canal 实现MySQL与Elasticsearch7数据同步

1 工作原理 canal 模拟 MySQL slave 的交互协议&#xff0c;伪装自己为 MySQL slave &#xff0c;向 MySQL master 发送 dump协议 MySQL master 收到 dump 请求&#xff0c;开始推送 binary log 给 slave (即 canal ) canal 解析 binary log 对象(原始为 byte 流) 优点&…

tensorflow基础

windows安装tensorflow anaconda或者pip安装tensorflow&#xff0c;tensorflow只支持win7 64系统&#xff0c;本人使用tensorflow1.5版本&#xff08;pip install tensorflow1.5&#xff09; tensorboard tensorboard只支持chrome浏览器&#xff0c;而且加载过程中可能有一段…

计算机竞赛 深度学习+opencv+python实现车道线检测 - 自动驾驶

文章目录 0 前言1 课题背景2 实现效果3 卷积神经网络3.1卷积层3.2 池化层3.3 激活函数&#xff1a;3.4 全连接层3.5 使用tensorflow中keras模块实现卷积神经网络 4 YOLOV56 数据集处理7 模型训练8 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &am…

jmeter学习文档

JMeter学习&#xff08;一&#xff09;工具简单介绍 一、JMeter 介绍 Apache JMeter是100%纯JAVA桌面应用程序&#xff0c;被设计为用于测试客户端/服务端结构的软件(例如web应用程序)。它可以用来测试静态和动态资源的性能&#xff0c;例如&#xff1a;静态文件&#xff0c;J…

BaseMapper 中的方法

BaseMapper 中的方法&#xff1a; 插入 int insert(T entity) - 插入一条记录。 删除 int deleteById(Serializable id) - 根据主键ID删除记录。 int deleteById(T entity) - 根据实体对象&#xff08;ID&#xff09;删除记录。 int deleteByMap(Map<String, Object> …

Easyui里的datagrid嵌入select下拉框

问题&#xff1a; 想使用datagird里嵌入select下拉框&#xff0c;并在提交form表单时获取datagrid选中的每行数据里的每个下拉框选中的值。 解决方案&#xff1a; 其中economicIssuesSelect使用下拉框&#xff0c;重点关注 initEconomicIssues(row)方法。这里的方法需要传递ro…

C语言基础知识点(八)联合体和大小端模式

以下程序的输出是&#xff08;&#xff09; union myun {struct { int x, y, z;} u;int k; } a; int main() {a.u.x 4;a.u.y 5;a.u.z 6;a.k 0;printf("%d\n", a.u.x); } 小端模式 数据的低位放在低地址空间&#xff0c;数据的高位放在高地址空间 简记&#xff…

微软(TTS)文本转语音服务API实现

此博客实现与java实现微软文本转语音&#xff08;TTS&#xff09;经验总结_java tts_${简简单单}的博客-CSDN博客之上&#xff0c;首先感谢博客源码的提供&#xff0c;本人在上面添加了一些详细的注释&#xff0c;方便大家跟好的理解和使用&#xff0c;毕竟我已经用原文调试了一…

云原生Kubernetes:pod进阶之资源管理与探针

目录 一、理论 1.pod的资源限制 2.健康检查&#xff08;探针Probe) 3.示例 二、实验 1.pod的资源限制 2.健康检查&#xff08;探针Probe) 三、问题 1.生成资源报错 2.api版本错误 3.echo N>/proc/sys/vm/drop_caches如何实现清理缓存 4.生成启动退出容器报错 5…

java版Spring Cloud+Mybatis+Oauth2+分布式+微服务+实现工程管理系统

鸿鹄工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离构建工程项目管理系统 1. 项目背景 一、随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大。为了提高工程管理效率、减轻劳动强度、提高信息处理速度和准确性&#xff0c;公司对内部工程管…

python教程:使用gevent实现高并发并限制最大并发数

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 import time import gevent from gevent.pool import Pool from gevent import monkey # 一&#xff0c;定义最大并发数 p Pool(20) # 二&#xff0c;导入gevent…