七七旧事：复盘并改变写博客的方式

两数之和：降低时间复杂度

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

这一道题我们要解决数组的检索与目标数的查询输出，最后输出下标，七七想到的第一个就是暴力法，也是学校中教的，如下图

class Solution {
    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[]{};
    }
}

暴力法不做解释，他的时间复杂度非常高

import java.util.HashMap; 
import java.util.Map;

// 定义Solution类
class Solution {
    // 定义twoSum方法，接收一个整数数组nums和一个目标整数target，返回包含两个元素的整数数组
    public int[] twoSum(int[] nums, int target) {
        // 创建一个HashMap实例，用于存储数组元素值和对应的索引
        Map<Integer, Integer> map = new HashMap<>();

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

            // 检查map中是否存在complement这个键
            if (map.containsKey(complement)) {
                // 如果存在，说明找到了两个数，返回它们的索引
                return new int[]{map.get(complement), i};
            }

            // 如果不存在，将当前元素及其索引存入map中
            map.put(nums[i], i);
        }

        // 如果遍历完数组都没有找到结果，返回一个空数组
        return new int[0];
    }
}

哈希最大优势：解决了暴力法时间复杂度非常高的问题，他省去了不必要的遍历。当然有没有和七七一样的疑问？HashSet为什么不行？

时间复杂度：

HashMap：O(n)（每个元素仅遍历一次）。

HashSet：O(n²)（需要额外遍历查找索引）。

空间复杂度：

HashMap：O(n)（存储键值对）。

HashSet：O(n)（仅存储唯一值）。

一目了然。

我遇到的问题

如何用更低的时间复杂度做出这个题目

它是什么

可以快速查找的工具

常见用法

找目标数，降低复杂度

我踩过的坑

用错哈希结构，使用了单target

总结

快速，低时间复杂度

‍