企业官网建设流程全解析

1.两数之和

题目

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6输出：[0,1]

• 解法一（双for循环暴力查找）

• 代码

  class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); i++) { int nums2 = target - nums[i]; for(int j=i+1;j<nums.size();j++){ if(nums[j]==nums2){ return{i,j}; } } } return{}; } };

  注意

• 1.vector<int>& nums（引用传递）

• 含义：传递的是原vector的引用（别名），不会创建新的副本。

• 优点：非常高效，节省了拷贝数据所需的时间和内存。

• 2.vector<int> nums（值传递）

• 含义：传递的是原vector的完整副本。

• 优点：在函数内部修改nums不会影响外部原始数据。

• 缺点：每次调用函数都需要复制整个vector。如果数据量大，会消耗大量时间和内存，在 LeetCode 中极易导致超时（Time Limit Exceeded）。

  • 注意：在函数内部对nums的任何修改，都会直接改变外部的原始数据。

  • 解法二（哈希查找）

  • 哈希表

  • 在 C++ 中，std::unordered_map（哈希表）提供了许多实用的成员函数。以下是在刷题时最常用的几类函数：

    unordered_map<int, int> hashtable

  • 1. 查找与访问

  • count(key)：返回key在 map 中出现的次数。因为 key 是唯一的，所以返回值只能是0（不存在）或1（存在）。常用于判断某个 key 是否存在。

  • find(key)：返回一个迭代器。如果找到，指向该元素；如果没找到，指向end()。

  • at(key)：返回 key 对应的 value。如果 key 不存在，会抛出异常（比直接用[]访问更安全）。

  • 2. 插入与修改

  • map[key] = value：如果 key 存在，则修改其 value；如果 key 不存在，则插入新的键值对。这是“两数之和”中最常用的写法。

  • insert({key, value})或emplace(key, value)：插入键值对。注意：如果 key 已存在，它们不会覆盖原有的 value（这与[]的行为不同）。

  • 3. 删除

  • erase(key)：删除指定 key 的键值对。

  • 4. 状态与容量

  • size()：返回 map 中当前有多少个键值对。

  • empty()：判断 map 是否为空，返回true或false。

  • clear()：清空 map 中的所有元素。

• 迭代器

• 在 C++ 中，迭代器（Iterator）可以理解为一种“智能指针”。它的主要作用是提供一种统一的方式来遍历和访问容器（如vector、unordered_map）中的元素，而不需要暴露容器内部的底层数据结构。

• 1. 迭代器是什么？

• 你可以把容器想象成一排储物柜，而迭代器就是指向某个具体储物柜的“指针”。

• 通过迭代器，你可以找到当前指向的储物柜里的内容。

• 你也可以让迭代器移动（例如it++），指向下一个储物柜。

• 2. 在unordered_map中，迭代器指向什么？

• 对于unordered_map<int, int>，它的每一个元素都是一个键值对（Key-Value pair）。
  在 C++ 底层，这个键值对被封装在一个std::pair结构中。因此，find()返回的迭代器，实际上是指向了这个pair结构。

• 3. 如何通过迭代器访问元素？

• 既然迭代器指向的是一个pair，你就可以通过箭头运算符->来分别获取 Key 和 Value：

• it->first：获取 Key（键）。

• it->second：获取 Value（值）。

代码

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int>hashtable; for(int i=0;i<nums.size();i++){ auto it =hashtable.find(target-nums[i]); if(it!=hashtable.end()){ return{i,it->second}; } else{ hashtable[nums[i]]=i; } } return{}; } };

需要注意的是，在本题中因为要寻找target-nums[i]在哈希表中是否出现过，因此将数组的值作为哈希表的键，利用find()能达到快查的效果。