题目描述：

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

提示：数组中只有一个对应的答案，且不能使用两次相同的元素，可以按任意顺序返回答案。

方法一 - 暴力循环 - O (n²)

本方法的时间复杂度是 O (n²)，其中n是数组nums的长度。

分析：

1. 代码使用了嵌套循环结构：

   • 外层 for 循环从索引 0 遍历到 n-1，执行次数为 O (n)
   • 内层 for循环对于外层的每个 i，从 i+1 遍历到 n-1，平均执行次数约为 O (n/2)

2. 时间复杂度计算：

   • 外层循环与内层循环的执行次数相乘，得O (n × n/2)=O (n²/2)，省略常数即为O (n²)
   • 循环内部的操作（判断两数之和、返回结果等）都是常数时间 O (1)，不影响整体复杂度

这种双重循环的解法是 两数之和问题的暴力解法，虽然实现简单，但在数组规模较大时效率较低。

代码：

    public int[] twoSum(int[] nums, int target) {
        for(int i = 0;i<nums.length;i++){
            for(int j = i+1;j<nums.length;j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{0,0};    // 返回错误数据 - 即未查找到对应结果
    }

方法二 - 哈希表数据结构 - O (n)

本方法的时间复杂度是 O(n)，其中n是数组nums的长度。

哈希表 - 数据结构：

哈希表（Hash Table），也称为散列表，是一种高效的键值对（Key-Value）存储数据结构，通过哈希函数将键（Key）映射到数组中的特定位置（索引），从而实现快速的插入、删除和查找操作，具体讲解请看其他专业的博客。

分析：

时间复杂度：

1. 循环执行次数：代码使用单循环遍历数组，从索引 0 到 n-1，共执行 n 次迭代，时间复杂度为 O (n)。

2. 哈希表操作：

   • 每次循环中包含两个核心操作：map.containsKey() 和 map.put()。
   • 在哈希表中，这两个操作的平均时间复杂度均为 O (1)（理想情况下，哈希函数分布均匀，无严重哈希冲突）。
   • 即使考虑最坏情况（极端哈希冲突导致链表过长），Java 的 HashMap 会在链表长度超过阈值后转为红黑树，此时操作时间复杂度为 O (log k)（k 为冲突元素数量），但整体仍远优于 O (n)。

3. 整体复杂度：

   • 循环次数与哈希表操作的总时间均为线性级别，因此整体时间复杂度为 O(n)。

空间复杂度：

• 空间复杂度为 O(n)，因为哈希表在最坏情况下需要存储数组中所有元素（当目标值是最后两个元素之和时）。

这种实现是两数之和问题的最优解法之一，通过「空间换时间」的策略，将暴力解法的 O (n²) 时间复杂度优化到了线性级别。

代码：

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