LeetCode 1.两数之和

刷题日记1今天刷了 LeetCode 的第一道经典题两数之和。虽然是入门题但非常适合用来理解「暴力枚举」和「哈希表优化」的思维差距也是算法的基础开胃题记录一下自己的解题思路。题目大意给一个数组和一个目标值找出数组里唯一一组和为 target 的两个数返回它们的下标。不能重复使用同一个元素。思路一暴力双重循环最直白的想法两层循环枚举所有两个数的组合匹配成功直接返回下标。优点是简单无脑、不容易出错缺点也很明显时间复杂度是O(n²)数据量大的时候会很慢。class Solution { public: vectorint twoSum(vectorint 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: vectorint twoSum(vectorint nums, int target) { unordered_mapint, 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 {}; } };解题小总结暴力法适合新手理解题意数据量大容易超时哈希表法空间换时间最优解日常刷题、面试首选先查询、后存入完美避免重复使用同一个元素算法刷题不在于刷得多而在于每道题都吃透思想。两数之和虽简单但「哈希查表」的思路可以套用在非常多数组题目里算是非常值得掌握的基础技巧。