# 0001. 两数之和 ## 题目地址(1. 两数之和) <https://leetcode-cn.com/problems/two-sum> ## 题目描述 ``` <pre class="calibre18">``` 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ``` ``` ## 前置知识 - 哈希表 ## 公司 - 字节 - 百度 - 腾讯 - adobe - airbnb - amazon - apple - bloomberg - dropbox - facebook - linkedin - microsoft - uber - yahoo - yelp ## 思路 最容易想到的就是暴力枚举，我们可以利用两层 for 循环来遍历每个元素，并查找满足条件的目标元素。不过这样时间复杂度为 O(N^2)，空间复杂度为 O(1)，时间复杂度较高，我们要想办法进行优化。我们可以增加一个 Map 记录已经遍历过的数字及其对应的索引值。这样当遍历一个新数字的时候去 Map 里查询，target 与该数的差值是否已经在前面的数字中出现过。如果出现过，那么已经得出答案，就不必再往下执行了。 ## 关键点 - 求和转换为求差 - 借助 Map 结构将数组中每个元素及其索引相互对应 - 以空间换时间，将查找时间从 O(N) 降低到 O(1) ## 代码 - 语言支持：JS ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} nums * @param {number} target * @return {number[]} */</span> <span class="hljs-keyword">const</span> twoSum = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums, target</span>) </span>{ <span class="hljs-keyword">const</span> map = <span class="hljs-keyword">new</span> <span class="hljs-params">Map</span>(); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { <span class="hljs-keyword">const</span> diff = target - nums[i]; <span class="hljs-keyword">if</span> (map.has(diff)) { <span class="hljs-keyword">return</span> [map.get(diff), i]; } map.set(nums[i], i); } }; ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(N)O(N)O(N) 更多题解可以访问我的LeetCode题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经37K star啦。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。