Created time
May 25, 2022 02:30 PM
date
status
category
Origin
summary
tags
type
URL
icon
password
slug
两数之和
给定一个整数数组
nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。只会存在一个有效答案。**进阶：**你可以想出一个时间复杂度小于 O(n^2) 的算法吗？相关标签：数组, 哈希表。Two Sum
Given an array of integers
nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Only one valid answer exists. Follow-up: Can you come up with an algorithm that is less than O(n^2) time complexity? Related Topics: Array, Hash Table.这题是给我们一个数组和目标值，让我们在数组中找到两个不同的数并且满足这两个数的和是等于目标值的，然后返回这两个数它们的下标。
题目已经保证一定有解了，所以不用考虑无解的情况。如果有多个解的话随便输出一个解就可以了。
这题很简单有很多方法。最容易想到的思路就是直接枚举暴力循环，然后如果和相等的话就返回，这个算法时间复杂度是，比较慢不太可取；也可以排序之后用双指针来做但是时间复杂度是，而且排序的话下标会变，可以用一个pair记录数值和下标，所以排序比较麻烦。那么有没有的做法呢？
一般在考虑算法问题的时候，最主要考虑的就是时间复杂度，在时间复杂度低的情况下再考虑空间复杂度。因为一般来说时间会比空间更紧张一些，这完全是经验之谈。所以我们应该尽量保证时间最低。
怎么来考虑这个问题呢？我们在一个一个枚举每个数的时候，我们其实希望去找的是每个数前面有没有某个数使得这个数加上前面那个数的和为目标值。相当于就是问我们前面有没有一个数它的值是等于目标值减去当前值，换句话说就是查询前面某个数有没有存在，所以可以用哈希表。
c++ map是但是unordered_map是的。因为Map底层是平衡树，unordered_map底层是哈希表。题目已经变成了求前面是否存在某个数了所以可以哈希表，哈希表可以在的时间找出一个数是不是存在。
那么基本思路就有了，我们开一个记录前面所有数的哈希表。从前往后扫描每扫描一个数就把这个数放进哈希表里面，然后每次查询一下哈希表里面有没有一个数等于目标值减去当前数，存在的话就把下标返回。每个数往哈希表里面最多插一次，每个数会查询哈希表一次，哈希表的插入和查询都是的操作，所以该算法时间复杂度总共就是。