算法题丨Two Sum
描述
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
示例
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
算法分析
难度:低
分析:要求给定的数组,查找其中2个元素,满足这2个元素的相加等于给定目标target的值。
思路:一般的思路,我们遍历数组元素,假设当前遍历的数组元素x,再次遍历x之后的数组元素,假设当前再次遍历的数组元素y,判断x+y是否满足target,如果满足,则返回x,y下标,否则继续遍历,直至循环结束。考虑这种算法的时间复杂度是O (n²),不是最优的解法。
跟前面几章类似,我们可以考虑用哈希表来存储数据,这里用C#提供的Hashtable来存储下标-对应值(key-value)键值对;
接着遍历数组元素,如果目标值-当前元素值存在当前的Hashtable中,则表明找到了满足条件的2个元素,返回对应的下标;
如果Hashtable没有满足的目标值-当前元素值的元素,将当前元素添加到Hashtable,进入下一轮遍历,直到满足上一条的条件。
代码示例(C#)
public int[] TwoSum(int[] nums, int target) { var map = new Hashtable(); ; for (int i = 0; i < nums.Length; i++) { int complement = target - nums[i]; //匹配成功,返回结果 if (map.ContainsKey(complement)) { return new int[] { (int)map[complement], i }; } map.Add(nums[i], i); } return null; }
复杂度
- 时间复杂度:O (n).
- 空间复杂度:O (1).
附录
文章作者:原子蛋
文章出处:https://www.cnblogs.com/lizzie-xhu/
个人网站:https://www.lancel0t.cn/
个人博客:https://blog.lancel0t.cn/
微信公众号:原子蛋Live+
扫一扫左侧的二维码(或者长按识别二维码),关注本人微信公共号,获取更多资源。
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Python 学习(二)
1. 数据类型 Python 中的变量不需要声明。每个变量在使用前都必须赋值,变量赋值以后该变量才会被创建。在 Python 中,变量就是变量,它没有类型,我们所说的"类型"是变量所指的内存中对象的类型。等号(=)用来给变量赋值。等号(=)运算符左边是一个变量名,等号(=)运算符右边是存储在变量中的值。多变量赋值:a = b = c = 1 或者 a, b, c = 1, 2, "mazaiting" Python中六个标准数据类型:Number(数字)、String(字符串)、List(列表)、Tuple(元组)、Sets(集合)、Dictionary(字典) Number(数字) 1). 数字类型有四种 int、float、bool、complex(复数)。 示例1: >>> a, b, c, d = 210, 4.4, True, 4+3j >>> print(type(a),type(b),type(c),type(d)) 打印结果1: 图1.png 示例2: >>> a = 11 >>> isinstan...
- 下一篇
算法题丨3Sum
描述 Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. 示例 Given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] 算法分析 难度:中分析:要求给定的数组,找出满足条件的3个元素组合,使得3个元素之和等于零。注意,元素不能重复(值可以相同)。思路:首先,我们需要对数组进行排序,比如数组排序后变为[-4, -1, -1, 0, 1, 2],我们判断第一个元素-4,判断它之后是否有2个元素的和等于4,如果有的话满足条件。因为数组已经排序,只要向当前元素之后查找即可,不用往前查找; 接下来,我们开始遍...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- Hadoop3单机部署,实现最简伪集群
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果