LeetCodeTop100(1)：两数之和

太过爱你忘了你带给我的痛 2023-07-18 09:53 13阅读 0赞

##### 1. 题目描述 #####

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。  
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**示例**:

> 给定 nums = \[2, 7, 11, 15\], target = 9  
> 因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
> 所以返回 \[0, 1\]

来源：力扣（LeetCode）  
原题传送门：[link][].

##### 2. 考察知识点 #####

HashMap

##### 3. 思路 #####

1.  很容易想到使用**暴力遍历**的方法，但是往往带来的时间空间复杂度都很高。暴力遍方式其时间复杂度为O(n^2)，空间复杂度：O(1)。
2.  第一种思路：对数组遍历时，在我们遇到第一个小于 target的数时，**就会再次遍历数组找到等于target-nums \[i\]的值，并返回数组下标。**
3.  换一种思路：对数组遍历时，在我们遇到第一个小于 target的数时，**如果能够直接找到符合target-nums \[i\]的值并返回数组下标就会快很多**。即通过value找到索引key，而数组是不具备这种功能的。
4.  于是想到哈希表，通过以空间换取速度的方式，我们可以将查找时间从 O(n)降低到 O(1)。

##### 4. 代码（Java） #####

class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], i);
            }
            for (int i = 0; i < nums.length; i++) {
                int complement = target - nums[i];
                if (map.containsKey(complement) && map.get(complement) != i) {
                    return new int[] { i, map.get(complement) };
                }
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    }

##### 5. 时间及空间复杂度 #####

*  时间复杂度：O(n)，  
    我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。
 *  空间复杂度：O(n)，  
    所需的额外空间取决于哈希表中存储的元素数量，该表中存储了n 个元素。

##### 6. 知识积累 #####

*  HashMap的常用命令: [link][link 1].

[link]: https://leetcode-cn.com/problems/two-sum
[link 1]: https://blog.csdn.net/weixin_43518038/article/details/105125433