算法入门：两数之和（Two Sum）----HashMap空间换时间经典题解

前言作为LeetCode入门第一道算法题两数之和堪称算法入门的经典题型不仅考察基础的数组遍历更能引出哈希表优化、空间换时间的核心算法思想也是面试中常考的基础算法题非常适合Java自学者用来夯实算法基础。1、题目描述给定一个整数数组 nums 和一个整数目标值 target 请你在该数组中找出和为目标值的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案但是数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例输入nums [2,7,11,15], target 9输出[0,1]解释因为 nums[0] nums[1] 9 返回 [0, 1] 。2、解题思路暴力解法基础思路直接两层for循环遍历数组两两相加判断是否等于target找到后返回下标。缺点时间复杂度O(n²)数据量大时效率极低。优化解法HashMap空间换时间核心思想利用HashMap存储已经遍历过的数字及其下标遍历数组时计算当前数字与target的差值直接在HashMap中查找该差值是否存在1. 初始化HashMap用于存储数组元素和对应下标​2. 遍历数组计算 target - 当前元素 的差值​3. 若差值存在于HashMap中直接返回HashMap中差值的下标和当前下标​4. 若不存在将当前元素和下标存入HashMap继续遍历该方法时间复杂度优化至O(n)仅遍历一次数组空间复杂度O(n)用少量空间换取时间效率。3、Java代码实现class Solution { public int[] twoSum(int[] nums, int target) { // 初始化哈希表key数组元素value元素下标 Integer,Integer hasht(); // 遍历数组 for (int i 0; i nums.length; i) { // 计算需要查找的目标差值 int temp target - nums[i]; // 判断哈希表中是否存在该差值 if(hashtable.containsKey(temp)){ // 存在则返回对应下标 return new int[]{hashtable.get(temp),i}; } // 不存在则将当前元素和下标存入哈希表 hashtable.put(nums[i],i); } // 无符合条件结果返回空数组 return new int[0]; } }4、代码解析4.1. 首先创建HashMap对象键存储数组中的数字值存储数字对应的数组下标​4.2. 遍历数组每遍历一个元素就计算需要匹配的差值​4.3. 通过 containsKey 方法快速查找差值是否已遍历过查找效率O(1)​4.4. 找到匹配值后直接返回两个下标未找到则将当前元素存入哈希表​4.5. 遍历结束无结果则返回空数组符合题目要求。5、算法总结这道题是哈希表应用的入门题核心掌握空间换时间的算法思想相比暴力解法HashMap的优化思路极大提升了执行效率也是后续解决同类查找类题目的核心思路。对于Java自学者来说吃透这道题不仅能掌握数组遍历、HashMap的基础使用更能建立算法优化的思维为后续学习更复杂的算法打下基础。持续更新Java自学、LeetCode刷题笔记零基础入门算法欢迎关注交流