外观
两数之和
⭐ 题目日期：
百度 - 2024/12/2
🌳 题目描述：
给定一个整数数组 nums 和一个目标值 target，在数组中找出和为目标值 target 的两个整数，并返回它们的数组下标。
示例 1：
输入：nums = [17, 6, 13, 8], target = 14
输出：[1, 3]
解释：能找到数组中的两个元素 6 和 8，满足它们的和 6 + 8 = 14（target），返回对应索引为 1, 3🕵🏽♂️ 面试评估：
这道题主要考察候选人能否找到合适的数据结构高效存储访问过的元素，从而完成对两个目标整数的查找。
🧗难度系数：
⭐️ ⭐️
📝思路分析：
这道题的要求是在数组中寻找出两个数以等于目标值 target，最直接的解法是使用双层循环来遍历整个数组，返回满足条件的数对。在这个过程中，如果每次访问一个新的元素时，都需要重新检查之前访问过的元素，检查是否有已出现的数字和当前数字相加等于目标值 target。这样的方法导致时间复杂度为 O(n²)，出现了大量的重复访问，效率低下。
那么是否存在一种更为高效的方法来定位前面满足条件的元素呢？我们可以用哈希表来解决问题。哈希表的查询平均时间复杂度为 O(1)，我们可以将已经访问过的元素存入哈希表，这样我们每遍历一个元素 X，只需检测 target - X 是否在哈希表里，如果在，表明元素对已找到；如果不在，将 X 存入哈希表用来匹配后面的元素。哈希表存 <key, value>，key 存具体的数值，value 存数值对应的索引。
具体过程如下：
- 在遍历数组的过程中，将当前元素存入哈希表，并将其索引作为值。
- 同时，计算与目标值的差值（即补数），并检查该补数是否已存在于哈希表中。
- 如果存在补数，说明当前元素与哈希表中的补数相加等于目标值，直接返回它们的索引。
以案例为例，分析如图所示。 
💻代码(Java、Python、C++)：
Java
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> result = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 计算与目标的差值
int complement = target - nums[i];
// 在 result 中查找，如果其中存在补数，返回两个下标
if(result.containsKey(complement)) {
return new int[]{result.get(complement), i};
}
// 将符合的组合放入 result
result.put(nums[i], i);
}
// 没找到结果 返回空值
return new int[0];
}Python
def twoSum(self, nums: List[int], target: int) -> List[int]:
result = {}
for i, num in enumerate(nums):
complement = target - num # 计算补数
if complement in result: # 查找补数是否在字典中
return [result[complement], i]
result[num] = i # 将当前数及其索引存入字典
return [] # 如果没有找到，返回空列表C++
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> result;
for (int i = 0; i < nums.size(); ++i) {
int complement = target - nums[i]; // 计算补数
// 如果找到补数，返回索引
if (result.find(complement) != result.end()) {
return {result[complement], i};
}
// 将当前值及索引存入 map
result[nums[i]] = i;
}
return {}; // 如果没有找到，返回空 vector
}🚵🏻复杂度分析：
- 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组，并在哈希表中进行查找和插入操作，平均时间复杂度为 O(1)。
- 空间复杂度：O(n)，哈希表用于存储数组中的元素及其索引，最多存储 n 个元素。