力扣经典150题第四十三题：两数之和
题目描述
给定一个整数数组 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]
解题思路
一种简单的解决方案是使用哈希表（HashMap）来存储每个元素的值及其索引。我们遍历数组，对于每个元素 nums[i]，计算目标值 complement = target - nums[i]。然后检查哈希表中是否存在 complement，如果存在则说明找到了答案，返回对应的索引。如果不存在，则将当前元素存入哈希表中。
完整代码
import java.util.HashMap; import java.util.Map; public class TwoSum { public int[] twoSum(int[] nums, int target) { // 创建哈希表，用于存储元素值和对应的索引 Map<Integer, Integer> map = new HashMap<>(); // 遍历数组 for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; // 检查哈希表中是否存在 complement if (map.containsKey(complement)) { // 找到了满足条件的两个数，返回它们的索引 return new int[] { map.get(complement), i }; } // 将当前元素存入哈希表中，值作为 key，索引作为 value map.put(nums[i], i); } // 如果未找到符合条件的两个数，返回空数组 return new int[] {}; } public static void main(String[] args) { int[] nums1 = {2, 7, 11, 15}; int target1 = 9; TwoSum solution = new TwoSum(); int[] result1 = solution.twoSum(nums1, target1); System.out.println("示例 1 结果：" + Arrays.toString(result1)); int[] nums2 = {3, 2, 4}; int target2 = 6; int[] result2 = solution.twoSum(nums2, target2); System.out.println("示例 2 结果：" + Arrays.toString(result2)); int[] nums3 = {3, 3}; int target3 = 6; int[] result3 = solution.twoSum(nums3, target3); System.out.println("示例 3 结果：" + Arrays.toString(result3)); } }
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需遍历一次数组，哈希表的插入和查找操作均为 O(1) 的时间复杂度。
- 空间复杂度：O(n)，其中 n 是数组 nums 的长度。哈希表最多存储 n 个元素。
总结与结语
本题利用哈希表的快速查找特性，通过一次遍历数组即可找到和为目标值的两个元素。这种解法的时间复杂度为 O(n)，空间复杂度也为 O(n)，是一种高效的解决方案。
哈希表的使用在解决数组和字符串相关的问题中具有广泛的应用，能够有效地降低时间复杂度。
通过掌握哈希表的基本原理和操作，能够更加高效地解决类似的算法问题，提高编程的技能和效率。
