LeetCode 1. 两数之和

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 1. 两数之和

思路分析

我们可以使用哈希表来解决这个问题。具体思路如下：

遍历数组 nums，对于每个元素 num，计算出需要的另一个数 needed，即 needed = target - num。

检查哈希表中是否存在 needed。如果存在，说明找到了两个数，返回它们的下标。

如果不存在，将当前元素 num 和它的下标存入哈希表中，以便后续查找。

这种方法的优点是可以在一次遍历中完成查找，效率较高。

参考代码

func twoSum(nums []int, target int) []int {
	hashtable := make(map[int]int)
	for i, num := range nums {
		needed := target - num
		if index, ok := hashtable[needed]; ok {
			return []int{index, i}
		}
		hashtable[num] = i
	}
	return []int{}
}

时间复杂度：O (n)，其中 n 是数组 nums 的长度。我们只遍历了一次数组。

空间复杂度：O (n)，最坏情况下，哈希表中存储了所有的元素。

🍏 点击查看 Java 题解

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = {-1, -1};
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                res[0] = map.get(target - nums[i]);
                res[1] = i;
                return res;
            }
            map.put(nums[i], i);
        }
        return res;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/24356627