云阳网站制作,网红网站建设官网,移动互联网开发的学习心得300字,wap网站模式文章目录 1. 两数之和题目描述哈希表#xff1a;map二分查找暴力#xff1a;双重for循环 1. 两数之和
题目描述
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你可… 文章目录 1. 两数之和题目描述哈希表map二分查找暴力双重for循环 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] 提示
2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案
进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗
哈希表map
使用map需要明确两点
map用来做什么map中key和value分别表示什么
map目的用来存放我们访问过的元素因为遍历数组的时候需要记录我们之前遍历过哪些元素和对应的下标这样才能找到与当前元素相匹配的也就是相加等于target
接下来是map中key和value分别表示什么。
这道题 我们需要 给出一个元素判断这个元素是否出现过如果出现过返回这个元素的下标。
那么判断元素是否出现这个元素就要作为key所以数组中的元素作为key有key对应的就是valuevalue用来存下标。
所以 map中的存储结构为 {key数据元素value数组元素对应的下标}。
在遍历数组的时候只需要向map去查询是否有和目前遍历元素匹配的数值如果有就找到的匹配对如果没有就把目前遍历的元素放进map中因为map存放的就是我们访问过的元素。
过程如下
class Solution {
public:vectorint twoSum(vectorint nums, int target) {// 创建一个哈希表来存储数组元素和它们的索引unordered_mapint, int map;//map.find() 返回的是一个迭代器std::unordered_mapint, int::iterator它存储的元素是 std::pairconst Key, T 类型的对象// 遍历数组中的每个元素索引为ifor (int i 0; i nums.size(); i) {//枚举a:这里其实是将abtarget转换为target-ab,然后在数组中查找b是否存在// 尝试在哈希表中找到与当前元素相加等于target的元素auto b map.find(target - nums[i]);// 如果找到了这样的元素if (b ! map.end()) {// 返回一个包含两个索引的数组i是当前元素的索引// b-second是之前存储在哈希表中的配对元素的索引return { i, b-second };}// 如果没有找到配对元素将当前元素的值和索引存入哈希表map.insert(pairint, int(nums[i], i));//相当于map[nums[i]]i;}// 如果没有找到任何满足条件的元素对返回一个空数组return {};}
}; autoauto 关键字用于自动类型推断。它指示编译器自动推断变量的类型根据变量的初始化表达式来确定其类型。 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:vectorint twoSum(vectorint nums, int target) {// 复制原数组nums到num2用于在排序后找回原始索引vectorint num2(nums.begin(), nums.end());// 对nums进行快速排序quick_sort(nums, 0, nums.size() - 1);vectorint num;// 遍历排序后的数组寻找是否存在两个数的和等于targetfor (int i 0; i nums.size(); i) {// 计算与当前数字nums[i]相配对的数字int b target - nums[i];// 使用二分查找法在nums中查找bint 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 vectorint();}// 快速排序算法的实现
private:void quick_sort(vectorint 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);// 如果ij交换两个元素if (i j) swap(nums[i], nums[j]);}// 递归地对左右子数组继续排序quick_sort(nums, l, j);quick_sort(nums, j 1, r);}// 二分查找算法的实现int find(int n, vectorint 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;}// 检查是否找到目标nif (nums[l] n) return l;return -1;}// 在原数组中查找给定的数字并返回其索引int find_xb(int v, vectorint 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:vectorint twoSum(vectorint nums, int target) {// 定义一个向量来存放结果vectorint 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 vectorint();}
};
