一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1358|回复: 12
收起左侧

[Leetcode] 4sum

[复制链接] |试试Instant~ |关注本帖
Struggling 发表于 2015-12-13 12:06:00 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int>> result;
if (num.size() < 4) return result;
sort(num.begin(), num.end());
unordered_map<int, vector<pair<int, int> > > cache;
for (size_t a = 0; a < num.size(); ++a) {
for (size_t b = a + 1; b < num.size(); ++b) {
cache[num[a] + num[b]].push_back(pair<int, int>(a, b));
}
}
for (int c = 0; c < num.size(); ++c) {
for (size_t d = c + 1; d < num.size(); ++d) {
const int key = target - num[c] - num[d];
if (cache.find(key) == cache.end()) continue;
const auto& vec = cache[key];
for (size_t k = 0; k < vec.size(); ++k) {
if (c <= vec[k].second)
continue; // 有重叠
result.push_back( { num[vec[k].first],
num[vec[k].second], num[c], num[d] });
}
}
}
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;

这是leetcode 4sum的参考答案之一,倒数第二句代码,我还是有点不太明白
result.erase(unique(result.begin(), result.end()), result.end());
unique返回的是去除duplicates的result,他是一个数组?不知道我有没有理解错
erase两个参数按道理应该第一个是开始擦除的起始位置,第二个是擦除操作的结束位置,但是unique返回的不是数组吗?这样就矛盾了!

求大神解答!!本人感激不尽!!
stellari 发表于 2015-12-15 00:33:45 | 显示全部楼层
Struggling 发表于 2015-12-14 05:29
还有一个问题
result.push_back( { num[vec[k].first], num[vec[k].second], num[c], num[d] });
参考 ...

用gcc的话,要保证你的版本支持c++11,并且编译的时候使用 -std=c++11 开关。另外,建议找本C++11的新语法的书或者网上教程来看看,很多你问的问题看完书以后都能迎刃而解了。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

 楼主| Struggling 发表于 2015-12-13 21:15:35 | 显示全部楼层
没有人看到吗?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-13 22:40:05 | 显示全部楼层
unique返回的不是数组,而是一个迭代器。具体来说,是从容器中删除掉一些元素后,“指向最后一个未被删除的元素的后一位置”的迭代器。比如[2, 3, 3, 5, 5],删除完以后数组变为[2, 3, 5, ?, ?]。unique返回的迭代器就是指向第一个?的位置。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| Struggling 发表于 2015-12-14 04:33:45 | 显示全部楼层
stellari 发表于 2015-12-13 22:40
unique返回的不是数组,而是一个迭代器。具体来说,是从容器中删除掉一些元素后,“指向最后一个未被删除的 ...

谢谢!能进一步给我解释下auto的用法吗?比如说这一句
const auto& vec = cache[key];
回复 支持 反对

使用道具 举报

 楼主| Struggling 发表于 2015-12-14 05:29:37 | 显示全部楼层
stellari 发表于 2015-12-13 22:40
unique返回的不是数组,而是一个迭代器。具体来说,是从容器中删除掉一些元素后,“指向最后一个未被删除的 ...

还有一个问题
result.push_back( { num[vec[k].first], num[vec[k].second], num[c], num[d] });
参考答案是这么写的,但是在linux环境下运行会报错,不知道怎么回事,
我改成了以下形式才运行成功 vector<int> temp;
          temp.push_back(num[vec[k].first]);
          temp.push_back(num[vec[k].second]);
          temp.push_back(num[c]);
          temp.push_back(num[d]);
          result.push_back(temp);
我想问问,参考答案上面的push_back方式没有办法实现是我代码问题吗?还是编译器问题?如果可以用参考答案用的方法,该做如何改动?
回复 支持 反对

使用道具 举报

 楼主| Struggling 发表于 2015-12-14 22:40:22 | 显示全部楼层
呜呜呜呜,都没有人回答我的问题!!
回复 支持 反对

使用道具 举报

 楼主| Struggling 发表于 2015-12-15 02:43:14 | 显示全部楼层
stellari 发表于 2015-12-15 00:33
用gcc的话,要保证你的版本支持c++11,并且编译的时候使用 -std=c++11 开关。另外,建议找本C++11的新语 ...

请问Gcc是什么?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-15 08:31:48 | 显示全部楼层

。。。那你在Linux下是用什么编译的?
回复 支持 反对

使用道具 举报

 楼主| Struggling 发表于 2015-12-15 09:02:14 | 显示全部楼层
stellari 发表于 2015-12-15 08:31
。。。那你在Linux下是用什么编译的?

忘记了,当时它自动安装了一个软件,我现在用emacs编译
回复 支持 反对

使用道具 举报

 楼主| Struggling 发表于 2015-12-15 09:03:52 | 显示全部楼层
stellari 发表于 2015-12-15 08:31
。。。那你在Linux下是用什么编译的?

大神,顺便帮我回答下这个问题吧!谢谢
http://www.1point3acres.com/bbs/thread-159569-1-1.html
问题见链接
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-15 17:16:50 | 显示全部楼层
Struggling 发表于 2015-12-15 09:02
忘记了,当时它自动安装了一个软件,我现在用emacs编译

先明确一个事情,Emacs只是编辑器,不是编译器。它只是代替你去调用gcc (g++)编译器而已。

还是建议你多熟悉一下c++的有关内容。如果你说自己在Linux下搞c++编程,但是不知道gcc/g++是什么,你100%不会拿到offer的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 12:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表