刷题日记1
今天刷了 LeetCode 的第一道经典题：两数之和。
虽然是入门题，但非常适合用来理解「暴力枚举」和「哈希表优化」的思维差距，也是算法的基础开胃题，记录一下自己的解题思路。
题目大意
给一个数组和一个目标值，找出数组里唯一一组和为 target 的两个数，返回它们的下标。不能重复使用同一个元素。
思路一：暴力双重循环
最直白的想法，两层循环枚举所有两个数的组合，匹配成功直接返回下标。
优点是简单无脑、不容易出错；缺点也很明显，时间复杂度是O(n²)，数据量大的时候会很慢。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(nums[i] + nums[j] == target){ return {i, j}; } } } return {}; } };
思路二：哈希表优化（最优 O(n)）
想要提速，核心就是用空间换时间。
我们只需要一次遍历数组：
对于当前数 nums[i]，我们需要找的另一个数就是：target - nums[i]。
用哈希表记录「数值对应下标」，每遍历一个数，先查表、再存表，就能一次性找到答案。
这种做法时间复杂度优化到O(n)，也是面试标准解法。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> mp; for(int i = 0; i < nums.size(); i++){ int need = target - nums[i]; if(mp.find(need) != mp.end()){ return {mp[need], i}; } mp[nums[i]] = i; } return {}; } };
解题小总结
暴力法：适合新手理解题意，数据量大容易超时
哈希表法：空间换时间，最优解，日常刷题、面试首选
先查询、后存入，完美避免重复使用同一个元素
算法刷题不在于刷得多，而在于每道题都吃透思想。两数之和虽简单，但「哈希查表」的思路可以套用在非常多数组题目里，算是非常值得掌握的基础技巧。
