1. 两数之和

题目：两数之和

描述：

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

你可以假设每种输入只会有 一个解，并且同样的元素不能被重复利用。

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

---

示例：

示例 1:

输入: nums = [2, 7, 11, 15], target = 9
输出: [0, 1]
解释: 因为 nums[0] + nums[1] == 9 ，返回 [0, 1]。

示例 2:

输入: nums = [3, 2, 4], target = 6
输出: [1, 2]

示例 3:

输入: nums = [3, 3], target = 6
输出: [0, 1]

---

最优解：

为了优化这个问题的解决方案，最常见的方法是使用哈希表。哈希表允许我们在常数时间内查找元素，因此可以使得整个算法的时间复杂度降至 O(n)，而不是暴力破解的 O(n²)。

算法步骤：

1. 创建一个空的哈希表，用于存储遍历过的数字和它们的索引。
2. 遍历数组 nums，对于每个元素 num，计算 target - num，检查哈希表中是否已经存在 target - num。
3. 如果存在，说明我们找到了两个数，它们的和为目标值，返回它们的下标。
4. 如果不存在，将当前元素 num 和它的索引加入哈希表中，继续遍历下一个元素。

代码实现：

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组长度
        int n = scanner.nextInt();
        int[] nums = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        // 读取目标值
        int target = scanner.nextInt();

        Solution solution = new Solution();
        int[] result = solution.twoSum(nums, target);

        // 输出结果
        System.out.println("[" + result[0] + ", " + result[1] + "]");

        scanner.close();
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建哈希表，存储数值和索引
        HashMap<Integer, Integer> map = new HashMap<>();

        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i]; // 计算目标值与当前数的差值

            // 如果差值已经在哈希表中，返回当前索引和差值的索引
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }

            // 如果没有找到，存储当前数和它的索引
            map.put(nums[i], i);
        }

        // 如果没有找到解，返回空数组
        throw new IllegalArgumentException("No solution found");
    }
}

---

时间复杂度分析：

• 时间复杂度：O(n)，我们只需要遍历一次数组，其中哈希表的查询和插入操作都是 O(1) 的时间复杂度。
• 空间复杂度：O(n)，我们使用了一个哈希表来存储元素和索引。

结论：

这个解法利用哈希表将查找时间压缩为常数时间，从而大幅优化了算法的时间复杂度，使其能够应对较大的数据集。