LeetCode 1:两数之和 Two Sum
题目:
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
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.
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
解题思路:
- 暴力穷举:外循环遍历每个元素
x
,内循环查找是否存在一个值与target - x
相等的目标元素,返回相等的目标元素和 x 的索引。时间复杂度 O (n^2),效率太低,pass。 -
哈希表:哈希映射(map、dict),key 保存该元素,value 保存该元素索引。
- 两次遍历法:第一次遍历把所有元素及其索引保存到哈希映射,第二次遍历查找
target - x
相等的目标元素 -
一次遍历法:假如
y = target - x
,则x = target -y
,所以一次遍历 在存入哈希映射的同时查找是否存在一个值与target - x
相等的目标元素。例:nums = [2, 11, 7, 15], target = 9, hashmap = { } 遍历: i = 0: target - x = 9 - 2 = 7, 7 不存在于 hashmap 中,则 x(2) 加入 hashmap, hashmap = {2 : 0} i = 1: target - x = 9 - 11 = -2, -2 不存在于 hashmap 中,则 x(-2) 加入 hashmap, hashmap = {2 : 0, 11 : 1} i = 2: target - x = 9 - 7 = 2, 2 存在于 hashmap 中,则返回列表 [2, 0]
- 两次遍历法:第一次遍历把所有元素及其索引保存到哈希映射,第二次遍历查找
代码:
两次遍历(Java):
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) {//一次遍历转换成键值对,key为元素值,value为索引值 map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) {//二次遍历查找符合条件的元素 int res = target - nums[i]; if (map.containsKey(res) && map.get(res) != i) {//查找到的目标元素不能为其本身 return new int[]{i, map.get(res)}; } } return null; } }
一次遍历 (Java):
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int res = target - nums[i]; if (map.containsKey(res)) {//因为自身元素还未加入到 hashmap,无需 map.get(res) != i 条件判断 return new int[]{i, map.get(res)}; } map.put(nums[i], i);//未找到目标元素则将其加入 hashmap } return null; } }
一次遍历 (Python):
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dic = {} for i, num in enumerate(nums): #枚举 nums 数组 if num in dic: return [dic[num], i] else: dic[target-num] = i
利用 Python 数组自带 index 方法解题:
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i, num in enumerate(nums): if target-num in nums and nums.index(target-num) != i: return [i, nums.index(target-num)]
list.index():
描述:
index () 函数用于从列表中找出某个值第一个匹配项的索引位置。
语法:
index () 方法语法:
list.index(x, start, end)
参数:
- x-- 查找的对象。
- start-- 可选,查找的起始位置。
- end-- 可选,查找的结束位置。
返回:
该方法返回查找对象的索引位置,如果没有找到对象则抛出异常。
欢迎关注微.信.公.众号: 爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Qt编写自定义控件63-水波效果
一、前言 几年前就一直考虑过写这个控件了,在9年前用C#的时候,就看到过别人用C#写了个水波效果的控件,挺好玩的,当时看了下代码用的二维数组来存储变换的图像像素数据,自从学了Qt以后,有过几次想要用Qt写一个版本,当时功力尚浅,尝试过了没写成功,我记得还有个用汇编写的dll提供调用,那个效率贼高,用CPU绘制的话效率相对来说低很多。前阵子一个好友-离心泵(QQ:33522)恰巧写了个,我在他的基础上改进了一些功能,增加了一些接口设置,比如提供参数可以控制水波的消失速度,扩散的速度,水波的面积大小以及水波的深度等。 二、实现的功能 1:可设置显示的图像 2:可设置衰减系数,控制消失速度,值越小水波消失越快 3:可设置折射系数,控制扩散速度,值越大水波扩散越快 4:可设置石头大小,控制水波面积,值越大水波面积越大 5:可设置石头重量,控制水波深度,值越大水波深度越浪 6:目前采用的是cpu运算和绘制,图片越小越流畅 三、效果图 四、头文件代码 #ifndef WAVEWATER_H #define WAVEWATER_H /** * 水波效果控件 作者:离心泵(QQ:33522) 整理:f...
- 下一篇
Java垃圾回收机制你还不明白?一线大厂面试必问的!
什么是自动垃圾回收? 自动垃圾回收是一种在堆内存中找出哪些对象在被使用,还有哪些对象没被使用,并且将后者删掉的机制。所谓使用中的对象(已引用对象),指的是程序中有指针指向的对象;而未使用中的对象(未引用对象),则没有被任何指针给指向,因此占用的内存也可以被回收掉。在用 C 之类的编程语言时,程序员需要自己手动分配和释放内存。而 Java 不一样,它有垃圾回收器,释放内存由回收器负责。本文接下来将介绍垃圾回收机制的基本过程。 标记 垃圾回收的第一步是标记。垃圾回收器此时会找出哪些内存在使用中,还有哪些不是。 上图中,蓝色表示已引用对象,橙色表示未引用对象。垃圾回收器要检查完所有的对象,才能知道哪些有被引用,哪些没。如果系统里所有的对象都要检查,那这一步可能会相当耗时间。 清除 这一步会删掉标记出的未引用对象。 内存分配器会保留指向可用内存的引用,以供分配新对象。 压缩 为了提升性能,删除了未引用对象后,还可以将剩下的已引用对象放在一起(压缩),这样就能更简单快捷地分配新对象了。 为什么需要分代垃圾收集? 之前说过,逐一标记和压缩 Java 虚拟机里的所有对象非常低效:分配的对象越多,垃圾...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Hadoop3单机部署,实现最简伪集群
- CentOS8编译安装MySQL8.0.19
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Mario游戏-低调大师作品
- CentOS6,CentOS7官方镜像安装Oracle11G