力扣经典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];// 检查哈希表中是否存在 complementif (map.containsKey(complement)) {// 找到了满足条件的两个数，返回它们的索引return new int[] { map.get(complement), i };}// 将当前元素存入哈希表中，值作为 key，索引作为 valuemap.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)，是一种高效的解决方案。

哈希表的使用在解决数组和字符串相关的问题中具有广泛的应用，能够有效地降低时间复杂度。

通过掌握哈希表的基本原理和操作，能够更加高效地解决类似的算法问题，提高编程的技能和效率。

感谢您阅读本文，希望本文能帮助您更好地理解和掌握解决这道经典的算法问题！