1. 两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
示例 2:
示例 3:
提示:
- 2 <= nums.length <= 10
- -10 <= nums[i] <= 10
- -10 <= target <= 10
- 只会存在一个有效答案
进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?
哈希表:map
使用map需要明确两点:
- map用来做什么
- map中key和value分别表示什么
map目的用来存放我们访问过的元素,因为遍历数组的时候,需要记录我们之前遍历过哪些元素和对应的下标,这样才能找到与当前元素相匹配的(也就是相加等于target)
接下来是map中key和value分别表示什么。
这道题 我们需要 给出一个元素,判断这个元素是否出现过,如果出现过,返回这个元素的下标。
那么判断元素是否出现,这个元素就要作为key,所以数组中的元素作为key,有key对应的就是value,value用来存下标。
所以 map中的存储结构为 {key:数据元素,value:数组元素对应的下标}。
在遍历数组的时候,只需要向map去查询是否有和目前遍历元素匹配的数值,如果有,就找到的匹配对,如果没有,就把目前遍历的元素放进map中,因为map存放的就是我们访问过的元素。
过程如下:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 创建一个哈希表来存储数组元素和它们的索引
unordered_map<int, int> map;//map.find() 返回的是一个迭代器(std::unordered_map<int, int>::iterator),它存储的元素是 std::pair<const Key, T> 类型的对象
// 遍历数组中的每个元素,索引为i
for (int i = 0; i < nums.size(); i++) {//枚举a:这里其实是将a+b=target转换为target-a=b,然后在数组中查找b是否存在
// 尝试在哈希表中找到与当前元素相加等于target的元素
auto b = map.find(target - nums[i]);
// 如果找到了这样的元素
if (b != map.end()) {
// 返回一个包含两个索引的数组,i是当前元素的索引,
// b->second是之前存储在哈希表中的配对元素的索引
return { i, b->second };
}
// 如果没有找到配对元素,将当前元素的值和索引存入哈希表
map.insert(pair<int, int>(nums[i], i));//相当于map[nums[i]]=i;
}
// 如果没有找到任何满足条件的元素对,返回一个空数组
return {};
}
};
-
auto:auto 关键字用于自动类型推断。它指示编译器自动推断变量的类型,根据变量的初始化表达式来确定其类型。
-
map.find():
- 如果键 target - nums[i] 存在于 map 中,find 函数返回一个迭代器,指向 unordered_map 中含有该键的键值对。
- 如果键不存在,find 函数返回一个特殊的迭代器 map.end(),这个迭代器指向 unordered_map 结尾的位置,这表明搜索失败。
-
pair:在C++中,pair 是一个结构,定义在 头文件中,它可以将两个值合并成一个单元。这两个值可以是不同的数据类型。pair 最常见的用途是在关联容器中,如 std::map 或 std::unordered_map,其中每个元素都是一个键值对。
-
pair 的构造函数接受两个参数,分别对应 pair 的两个成员:first 和 second,其中:
- first 成员变量将存储键(nums[i]),
- second 成员变量将存储与键关联的值(i)。
-
二分查找
这道题并不推荐二分,因为需要考虑的东西太多:
- 使用二分算法查找需要对数组排序,一旦排序就会破坏原来的下标,我这里用一个新的num2复制 nums 数组,因为后面会对 nums 进行排序,这样做是为了保留原始元素的索引。
- 因为下标的变动还需要使用num2去寻找原来的下标
- 寻找原来下标中也有坑,如果两个数相同,就需要从下一个数开始寻找,不然会得到相同的下标:如下
// 如果两个找到的数字相同,需要找到第二个相同数字的索引
if (nums[i] == nums[z]) v = v + 1;
else v = 0;
总代码如下,比较复杂,所以并不推荐二分,因为一开始感觉像我做过的A-B 数对这道题,觉得可以用二分查找做出来,仅此记录而已
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 复制原数组nums到num2,用于在排序后找回原始索引
vector<int> num2(nums.begin(), nums.end());
// 对nums进行快速排序
quick_sort(nums, 0, nums.size() - 1);
vector<int> num;
// 遍历排序后的数组,寻找是否存在两个数的和等于target
for (int i = 0; i < nums.size(); i++) {
// 计算与当前数字nums[i]相配对的数字
int b = target - nums[i];
// 使用二分查找法在nums中查找b
int z = find(b, nums);
cout << z << endl;
// 如果找到了b,并且它的索引不是i(确保不是同一个元素)
if (z != -1 && z != i) {
// 查找nums[i]在原数组num2中的索引
int v = find_xb(0, num2, nums[i]);
num.push_back(v);
// 如果两个找到的数字相同,需要找到第二个相同数字的索引
if (nums[i] == nums[z]) v = v + 1;
else v = 0;
// 查找nums[z]在原数组num2中的索引
num.push_back(find_xb(v, num2, nums[z]));
// 返回结果数组,包含两个找到的索引
return num;
}
// 如果没有找到,则继续循环
else continue;
}
// 如果没有找到任何匹配的元素对,返回一个空数组
return vector<int>();
}
// 快速排序算法的实现
private:
void quick_sort(vector<int>& nums, int l, int r) {
// 如果子数组长度为0或1,则返回
if (l >= r) return;
// 初始化指针和基准值
int i = l - 1, j = r + 1, x = nums[(l + r) >> 1];
while (i < j) {
// 移动左指针直到找到一个大于等于x的元素
do i++; while (nums[i] < x);
// 移动右指针直到找到一个小于等于x的元素
do j--; while (nums[j] > x);
// 如果i<j,交换两个元素
if (i < j) swap(nums[i], nums[j]);
}
// 递归地对左右子数组继续排序
quick_sort(nums, l, j);
quick_sort(nums, j + 1, r);
}
// 二分查找算法的实现
int find(int n, vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= n) r = mid;
else l = mid + 1;
}
// 检查是否找到目标n
if (nums[l] == n) return l;
return -1;
}
// 在原数组中查找给定的数字并返回其索引
int find_xb(int v, vector<int>& num, int n) {
// 从给定的起始索引v开始查找
for (int i = v; i < num.size(); i++) {
// 如果找到了,就返回索引
if (num[i] == n)
return i;
}
// 这个循环理论上不会运行到结尾,因为前面的逻辑保证了n在num中
// 这里没有返回值,实际上应该有一个返回值来保证函数完整性
return -1; // 增加默认返回值
}
};
暴力:双重for循环
该代码的工作原理是:
- 遍历数组 nums 中的每个元素,索引为 i。
- 对于每个 i,再次遍历其之后的每个元素,索引为 j。
- 对于每对 (i, j),检查 nums[i] 和 nums[j] 的和是否等于 target。
- 如果找到这样的一对 (i, j),则将它们的索引作为答案返回。
- 如果遍历完所有的元素对也没有找到满足条件的对,那么返回一个空的数组。
时间复杂度和空间复杂度分析:
- 时间复杂度:O(n^2),因为有两个嵌套循环,每个循环都可能遍历整个数组 nums。
- 空间复杂度:O(1),因为除了存储结果所需的空间之外,不需要额外的存储空间。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 定义一个向量来存放结果
vector<int> num;
// 外层循环遍历数组中的每一个元素,除了最后一个
for (int i = 0; i < nums.size() - 1; i++) {
// 内层循环从当前元素的下一个开始遍历
for (int j = i + 1; j < nums.size(); j++) {
// 检查当前对的元素和是否等于目标值
if (nums[i] + nums[j] == target) {
// 如果等于目标值,则将两个数字的索引添加到结果向量中
num.push_back(i);
num.push_back(j);
// 返回结果,不需要继续查找
return num;
}
}
}
// 如果没有找到符合条件的两个数,返回空向量
return vector<int>();
}
};