🔗 两数之和
📌 题目描述
给定一个整数数组
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]
⚠️ 提示
2 <= nums.length <= 10⁴-10⁹ <= nums[i] <= 10⁹-10⁹ <= target <= 10⁹- 只会存在一个有效答案
💡 解法：哈希表
class Solution {
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];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
return new int[0];
}
}
📊 复杂度分析
- 时间复杂度：O(n) —— 一次遍历
- 空间复杂度：O(n) —— 哈希表存储最多 n 个元素
🧩 解题思路简述
遍历数组，对每个元素
nums[i]，计算其“补数”target - nums[i]，检查是否已在哈希表中：
- 若存在 → 找到答案，返回下标
- 若不存在 → 将
nums[i]和其下标存入哈希表利用哈希表实现 O(1) 查找，将暴力 O(n²) 优化为 O(n)。
文末附加内容
