# 菜鸟的coding · Day 000
两数之和（Two Sum）
题目
给定一个整数数组 nums 和一个整数目标值 target，
请你在该数组中找出 和为目标值 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，且同一个元素不能重复使用。
思路
朴素解法是两层循环枚举所有对 O(n²)，但可以用
哈希表优化到 O(n)：
遍历数组，对每个元素 x 检查 target - x 是否已经在哈希表里。
如果在，直接返回两个下标；否则把 x 的值和下标存入哈希表。
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen; // 哈希表：{数值 → 下标}
for (int c = 0; c < (int)nums.size(); c++) {
int complement = target - nums[c];
if (seen.count(complement)) {
return {seen[complement], c};
}
seen[nums[c]] = c;
}
return {}; // 题目保证有解，不会执行到这里
}
};
// --- 验证 ---
// twoSum([2, 7, 11, 15], 9) → [0, 1]
// twoSum([3, 2, 4], 6) → [1, 2]复杂度分析
- 时间复杂度：O(n)，只遍历一次数组。
- 空间复杂度：O(n)，哈希表最多存 n 个元素。
今日感受
很经典的入门题。第一反应确实是暴力双循环，但仔细想一下
"我需要的另一半在不在？"这个问题，就自然引导到哈希表了。
哈希查找是 O(1)，整体降到 O(n)——这种"用空间换时间"的思维值得记住。
今天是第一天，希望能坚持下去。就算某天只有10分钟，也要打开编辑器。