LeetCode题目笔记——1.两数之和
文章目录
- 题目描述
- 题目难度——简单
- 方法一:暴力
- 代码/Python
- 方法二:哈希表
- 代码/Python
- 代码/C++
- 总结
题目描述
这道题可以说是力扣的入坑题了,很经典,好像还是面试的经典题。
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]
提示:
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?
题目链接
题目难度——简单
方法一:暴力
最简单的方法就是无脑暴力,虽然看数组长度可能会失败,但平均下来找到答案时两个下标的差距的期望应该不大,可以暴力一试。用两个循环,每次判断两个数相加是否为target。
代码/Python
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:res = []n = len(nums)for i in range(n):for j in range(n):if i != j and nums[i] + nums[j] == target:res.append(i)res.append(j)return resreturn [-1, -1]
方法二:哈希表
我们可以只用一次循环就找到答案,在一次遍历中,对每个x,问题可以变成在数组中找target-x的坐标,如果我们能知道过去遍历过的数的位置i,那么答案就显然是当前位置和i,否则我们继续往前遍历,并记录当前元素的位置。所以我们需要一个字典。
代码/Python
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:res = [-1, -1]n = len(nums)pos = dict()for i in range(n):tmp = target - nums[i]if tmp in pos:res[0], res[1] = i, pos[tmp]return reselse:pos[nums[i]] = ireturn res
代码/C++
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> res(2);unordered_map<int, int> pos;int i, tmp;for(i = 0; i < nums.size(); i++){tmp = target - nums[i];if(pos.count(tmp) != 0){res[0] = i;res[1] = pos[tmp];return res;}else{pos[nums[i]] = i;}}return res;}
};
总结
第一种暴力,所以时间是O(N2),空间是O(1),第二种遍历一次,时间是O(N), 使用了字典,所以空间是O(N)。
相关文章:

LeetCode题目笔记——1.两数之和
文章目录题目描述题目难度——简单方法一:暴力代码/Python方法二:哈希表代码/Python代码/C总结题目描述 这道题可以说是力扣的入坑题了,很经典,好像还是面试的经典题。 给定一个整数数组 nums 和一个整数目标值 target,…...
CSDN版的详细MarkDown的使用教程
MarkDown的使用欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释…...

Nextcloud通过不被信任的域名访问解决方法 Nextcloud 您正在访问来自不信任域名的服务器
windows电脑在网页端输入“http://192.168.xxx.xxx:8080/login”访问远程ubuntu18.04服务器,访问其docker镜像的Nextcloud,提示“”Nextcloud通过不被信任的域名访问解决方法 Nextcloud 您正在访问来自不信任域名的服务器“”,如下图…...

Set集合的特点,HashSet去重的几个重要问题
Set集合的特点:无下标,无序(新增顺序和遍历顺序不一致,新增顺序不影响遍历顺序,而且有一个固定顺序),去重(不允许重复记录)public class TestOne {public static void main(String[] args) {// Set集合的特点ÿ…...

云计算|OpenStack|社区版OpenStack安装部署文档(十一--- 如何获取镜像---Rocky版)
前言: 前面我们使用虚拟机搭建了一个openstack集群,也就是在VM虚拟机的基础上模拟了一个简单的基于openstack社区版Rocky的私有云,但,不管任何部署安装工作,最后其实都是需要有实际的应用的,也就是常说的实…...
UmiJS学习
UmiJS4学习笔记起步官网学习:https://umijs.org/开发环境Umi.js 需要使用 Node.js来进行开发,因此请先确保电脑已经安装了 Node.js 且版本在 14 以上。安装pnpm:npm install pnpm -g创建项目Umi 官方提供了一个脚手架 ,可以轻松快…...
Leetcode:322. 零钱兑换(C++)
目录 问题描述: 实现代码与解析: 动态规划(完全背包): 原理思路: 问题描述: 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金…...

C经典小游戏之扫雷
编译环境:VS022 目录 1.算法思路 2.代码模块 2.1 game.h 2.2 game.cpp 2.3 test.cpp 3.重点分析 4.金句省身 1.算法思路 主要采用二维数组进行实现,设置两个二维数组,一个打印结果,即为游戏界面显示的效果,一个用…...

第十节 使用设备树插件实现RGB 灯驱动
Linux4.4 以后引入了动态设备树(Dynamic DeviceTree),我们这里翻译为“设备树插件”。设备树插件可以理解为主设备树的“补丁”它动态的加载到系统中,并被内核识别。例如我们要在系统中增加RGB 驱动,那么我们可以针对R…...
【LeetCode】公交路线 [H](宽度优先遍历)
815. 公交路线 - 力扣(LeetCode) 一、题目 给你一个数组 routes ,表示一系列公交线路,其中每个 routes[i] 表示一条公交线路,第 i 辆公交车将会在上面循环行驶。 例如,路线 routes[0] [1, 5, 7] 表示第 …...

报表生成器 FastReport .Net 用户指南 2023(十):Band的属性
FastReport .Net是一款全功能的Windows Forms、ASP.NET和MVC报表分析解决方案,使用FastReport .NET可以创建独立于应用程序的.NET报表,同时FastReport .Net支持中文、英语等14种语言,可以让你的产品保证真正的国际性。 FastReport.NET官方版…...

DAMA数据管理知识体系指南之文档和内容管理
第10章 文档和内容管理 10.1 简介 文档和内容管理是对存储在关系数据库以外的信息的采集、存储、访问以及使用的控制活动。文档和内容管理的侧重点在完整性和访问控制上。因此,它与关系数据库的数据操作管理大致相同。由于多数非结构化数据与存储在结构化文件中的…...
C++入门:数据结构
C/C 数组允许定义可存储相同类型数据项的变量,但是结构是 C 中另一种用户自定义的可用的数据类型,它允许您存储不同类型的数据项。结构用于表示一条记录,假设您想要跟踪图书馆中书本的动态,您可能需要跟踪每本书的下列属性&#x…...

C语言实现烟花表白,内含源码!!
虽然现在看烟花有一定难度,但代码式烟花可以随时随地看! 烟花的代码很多,实际上是可以用 Python、HTML5 等语言写烟花,但今天主要想和大家分享用C语言写的烟花代码,非常细致和实用。 同学们一定要亲自敲一遍…...

虚拟机安装CentOS 7(带界面)
目录 一、虚拟机安装CentOS 7(带界面) 1、打开下好的VMware,点击创建虚拟机 2、下一步 3、点击下一步 4、选择Linux,ContOS7,点击下一步 5、修改虚拟机名称和路径 6、下一步 7、点击自定义硬件 8、设置虚拟机大…...

Java测试——selenium具体操作
selenium的前置准备工作可以参考我之前的博客:Java测试——selenium的安装与使用教程 这篇博客讲解一下selenium的常见操作 先创建driver ChromeDriver driver new ChromeDriver();输入网址 driver.get("https://www.baidu.com");常见操作 查找元素…...

电子器件系列32:逻辑与门芯片74LS11
一、编码规则 先看看这个代码的意思:74LS11 74是一个系列(74 表示为工作温度范围,74: 0 ~ 70度。) ls的意思就是工艺类型(Bipolar(双极)工艺) 11是代码 什么是74系列逻辑芯片? - 知乎 什么是…...

LeetCode-101. 对称二叉树
目录题目分析递归法题目来源 101. 对称二叉树 题目分析 首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一…...
使用intlinprog求解指派问题MATLAB代码分享
% 输入指派矩阵C [3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10];f C(:); %生成一个列向量,作为目标函数系数,matlab默认以列排序[m,n] size(C);Aeq zeros(2*n,n*n); %2*n个等式约束,n*n个变量for i 1:n %这里先生成的是后5个…...

Spark On YARN时指定Python版本
坑很多,直接上兼容性最佳的命令,将python包上传到hdfs或者file:/home/xx/(此处无多余的/) # client 模式 $SPARK_HOME/spark-submit \ --master yarn \ --deploy-mode client \ --num-executors 2 \ --conf "spark.yarn.dist.archives<Python包…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...

android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)
名人说:莫道桑榆晚,为霞尚满天。——刘禹锡(刘梦得,诗豪) 原创笔记:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 上一篇:《数据结构第4章 数组和广义表》…...
GeoServer发布PostgreSQL图层后WFS查询无主键字段
在使用 GeoServer(版本 2.22.2) 发布 PostgreSQL(PostGIS)中的表为地图服务时,常常会遇到一个小问题: WFS 查询中,主键字段(如 id)莫名其妙地消失了! 即使你在…...