[LeetCode][1. 两数之和] 2种方法：暴力 和 HashMap

By Long Luo

1. 两数之和 题解。

方法一：暴力枚举

思路及算法：

最容易想到的方法是使用两层循环，第一层循环枚举数组中的每一个数 $x$，下一层循环在 $x$ 之后的元素中寻找数组中是否存在 $\textit{target} - x$。

    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

复杂度分析

• 时间复杂度：$O(N^2)$，其中 $N$ 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：$O(1)$。

方法二：哈希表

思路及算法：

方法一的时间复杂度较高的原因是寻找 $\textit{target} - x$ 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用 $\texttt{HashMap}$，可以将寻找 $\textit{target} - x$ 的时间复杂度降低到从 $O(N)$ 降低到 $O(1)$。

这样我们创建一个哈希表，对于每一个$x$，我们首先查询哈希表中是否存在 $\textit{target} - x$，然后将 $x$ 插入到 $\texttt{HashMap}$ 中，即可保证不会让 $x$ 和自己匹配。

public static int[] twoSum(int[] nums, int target) {
    int[] ans = new int[2];
    int n = nums.length;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        if (map.containsKey(target - nums[i])) {
            ans[0] = i;
            ans[1] = map.get(target - nums[i]);
            return ans;
        }
        map.putIfAbsent(nums[i], i);
    }

    return ans;
}

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组中的元素数量。对于每一个元素 $x$，我们可以 $O(1)$ 地寻找 $\textit{target} - x$。
• 空间复杂度：$O(N)$，其中 $N$ 是数组中的元素数量。主要为哈希表的开销。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗