欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCodeTop100(1):两数之和

程序员文章站 2024-03-22 14:56:28
...
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.