➕ 两数之和

📝 题目描述

​ 给你一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

​ 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现，例如索引为[2]的元素6不能在target为12时使用两次，即不能输出[2,2]。

​ 你可以按任意顺序返回答案。

📋 代码模板

class Solution {
    public int[] twoSum(int[] nums, int target) {

    }
}

💡 提示

1. $2<=nums.length<={10}^4$
2. ${-10}^9<=nums[i]<={10}^9$
3. ${-10}^9<=target<={10}^9$
4. 只会存在一个有效答案

🚀 示例

🖊️ 题解

暴力

​ 该题做简单的解法就是暴力：遍历数组nums中的每一个数nums[i]，寻找数组中是否存在target - nums[i]的其它数。当我们遍历数组寻找target - nums[i]时，由于每一个位于nums[i]之前的元素已经与nums[i]匹配过了，因此我们只需要在nums[i]之后寻找target - nums[i]即可。

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

哈希表

​ 暴力解法的时间复杂度较高，原因在于其寻找target - nums[i]这个过程需要额外再遍历一次数组。而利用哈希表，我们可以将这个过程的时间复杂度从 $O(n)$ 降低至 $O(1)$，具体做法如下。

1. 创建一个哈希表，以构建值target - nums[i]与索引i的映射。

2. 遍历数组nums，对于每个数nums[i]，算出其与target的差值，并将差值作为键查找哈希表，若存在，则返回结果，反之将差值与索引存入哈希表中。

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

💭 复杂度分析

​ 基于暴力的解决方案的复杂度分析如下。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(1)$。

​ 基于哈希表的解决方案的复杂度分析如下。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。