巧用Map解决两数之和问题 | IT宅-帅旋的专业知识分享

巧用Map解决两数之和问题

发布于 2024-03-13 | 更新于 2024-08-21

数组

20

哈希表

3

题目：1. 两数之和^[1]

如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

这也是一道经典的算法题：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

注意，这里是返回目标元素的下标。

解题思路

最简单的暴力双重循环肯定可以找到结果，但是这肯定不满足时间复杂度要求。

为了高效解决这个问题，我们可以使用哈希表来降低查找时间，哈希表支持以接近常数的平均时间复杂度进行查找操作。

具体步骤：

1. 初始化一个哈希表 Map<Integer, Integer>；
2. 遍历数组 nums 的每个元素；
3. 对于每个元素 x，检查 target - x 是否已经在哈希表中；
4. 如果 target - x 在哈希表中，那么我们找到了一对符合条件的元素，返回它们的索引；
5. 如果 target - x 不在哈希表中，将当前元素 x 及其索引添加到哈希表中，以便后续查找；
6. 重复步骤 3-5，直到找到答案。

Java解法

下面是使用Java语言的解法：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int ans = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(ans), i};
            }
          	// 注意，这里的value存储的是元素下标
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}

References

---

1. 1. 两数之和. Retrieved from https://leetcode.cn/problems/two-sum/ ↩︎

三大利器解决三数之和问题

动态规划经典案例：爬楼梯