网站首页 > 资源文章 正文
首发地址:https://www.xichunling.com/?p=42
解法一
两层循环,时间复杂度O(n^2),空间复杂度O(1)。
执行时间244ms,内存消耗9.3MB。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
int len = nums.size();
for (int i = 0; i < len; i ++) {
for (int j = i + 1; j < len; j ++) {
if (target - nums[i] == nums[j]) {
ret.insert(ret.begin(), i);
ret.insert(ret.begin()+ 1, j);
break;
}
}
if (ret.size() == 2) {
break;
}
}
return ret;
}
};
解法二
map记录数组元素与下标的映射关系,遍历一遍数组求解。时间复杂度O(n),空间复杂度O(n)。
执行时间20ms,内存消耗10.1MB。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
map<int, int> mapnum;
int len = nums.size();
for (int i = 0; i < len; i ++) {
int key = target - nums[i];
map<int, int>::iterator it = mapnum.find(key);
if (it == mapnum.end()) {
mapnum.insert(pair<int, int>(nums[i], i));
} else {
ret.insert(ret.begin(), mapnum.find(key)->second);
ret.insert(ret.begin() + 1, i);
break;
}
}
return ret;
}
};
解法三
用unordered_map构造映射,比map更快。因为map是用红黑树实现的,数据插入里面会排好序,搜索过程的时间复杂度为O(logn)。而unordered_map是用哈希表实现的,查找元素的时间复杂度为O(1)。
map适用于对内存大小敏感或数据要求有序性的情况;unordered_map适用于对查询效率要求较高的情况。
总得来说,这种解法的时间复杂度O(n),空间复杂度O(n)。耗时4ms,内存消耗10.3MB。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
unordered_map<int, int> unorderedmap;
int len = nums.size();
for (int i = 0; i < len; i ++) {
unorderedmap[nums[i]] = i;
}
for (int i = 0; i < len; i ++) {
int key = target - nums[i];
if (unorderedmap.count(key) && unorderedmap[key] != i) {
ret.push_back(i);
ret.push_back(unorderedmap[key]);
break;
}
}
return ret;
}
};
猜你喜欢
- 2024-10-19 亚马逊VC运营常见问题大揭秘:入门到精通的必备指南(上)
- 2024-10-19 收到亚马逊的 PO,能否不发货?(亚马逊包裹没收到怎么处理)
- 2024-10-19 那些关于亚马逊FBA库存backordered的误解,看看你是否也深受困扰
你 发表评论:
欢迎- 最近发表
- 标签列表
-
- 电脑显示器花屏 (79)
- 403 forbidden (65)
- linux怎么查看系统版本 (54)
- 补码运算 (63)
- 缓存服务器 (61)
- 定时重启 (59)
- plsql developer (73)
- 对话框打开时命令无法执行 (61)
- excel数据透视表 (72)
- oracle认证 (56)
- 网页不能复制 (84)
- photoshop外挂滤镜 (58)
- 网页无法复制粘贴 (55)
- vmware workstation 7 1 3 (78)
- jdk 64位下载 (65)
- phpstudy 2013 (66)
- 卡通形象生成 (55)
- psd模板免费下载 (67)
- shift (58)
- localhost打不开 (58)
- 检测代理服务器设置 (55)
- frequency (66)
- indesign教程 (55)
- 运行命令大全 (61)
- ping exe (64)
本文暂时没有评论,来添加一个吧(●'◡'●)