呼伦贝尔市网站建设_网站建设公司_数据备份_seo优化

🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

<<Git>><<MySQL>>

🌟心向往之行必能至

🚀 经典算法入门：两数之和

💡 题目解析

给定一个整数数组nums和一个目标值target，我们需要在数组中找到两个数，使它们的和等于target，并返回这两个数的下标。

• 每种输入只会对应一个答案
• 不能使用同一个元素两次

举个例子：

• 输入：nums = [2,7,11,15],target = 9
• 输出：[0,1]
• 解释：因为nums[0] + nums[1] = 2 + 7 = 9，所以返回它们的下标[0, 1]。

🛠️ 解法一：暴力枚举

这是最容易想到的思路，直接用两层循环遍历所有可能的数对，检查它们的和是否等于目标值。

cpp

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²)，因为两层循环，最坏情况下需要检查n*(n-1)/2个数对。
• 空间复杂度：O(1)，只使用了常数额外空间。

这种方法的优点是思路简单，但缺点也很明显 —— 当数组很大时，时间效率会变得很低。

⚡ 解法二：哈希表优化

为了把时间复杂度降到O(n)，我们可以用哈希表（unordered_map）来存储已经遍历过的数字及其下标。这样，对于每个数字nums[i]，我们只需要在哈希表中查找是否存在target - nums[i]，就能在O(1)时间内找到另一个数。

cpp

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hashMap; for (int i = 0; i < nums.size(); ++i) { int complement = target - nums[i]; if (hashMap.find(complement) != hashMap.end()) { // 找到互补数，返回结果 return {hashMap[complement], i}; } // 没找到就把当前数存入哈希表 hashMap[nums[i]] = i; } return {}; // 题目保证有解 } };

复杂度分析

• 时间复杂度：O(n)，我们只遍历了数组一次，哈希表的查找和插入操作都是O(1)。
• 空间复杂度：O(n)，最坏情况下需要存储整个数组的元素。

这种方法用空间换时间，是算法优化中非常常见的思路。

🎯 核心思路对比

这道题的关键在于理解空间与时间的权衡。当你需要更快的速度时，哈希表是一个非常强大的工具。