由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 大家帮忙看看这个4sum怎么就不对
相关主题
关于priority_queue一问请问下leetcode的two sum题目
Facebook Phone InterviewL的onsite冤了
Max Points on a Line 用c++map老是没法compile问surrounded region
问一下careercup一道题另开一贴unordered_set 对于 vector 和 pair 的has
C++高手看下这个LC的LRU Cache的实现刷题弱人来问个two sum的题目
Two problems from Google再讨论一个面试难题
报个G的电面all my baozi for people can give some answer to the question
写的LRU通不过大数据,帮忙看看给定一个值和sorted队列,找到所有pair(其和等于给定值)
相关话题的讨论汇总
话题: int话题: vector话题: num话题: iter话题: pair
进入JobHunting版参与讨论
1 (共1页)
g***j
发帖数: 1275
1
基本思路就是,先把两个的和存起来,并且把相应的index pair存到对应的直的map里
面去。
然后再把所有的两个的和和target的差算出来,去map里面找,因为map里面同样保存了
签名的数字的index,所以,只要后面两个数的最小的index比已有的最大的index大的
时候,就能保证不重复了。
可惜small set 15个总有一个不过,而且,因为显示问题,看不到哪个不过。哪个大侠
帮我看看代码?
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = num.size();
vector > results;
if(n <= 3) return results;
map > > myMap;
map > >::iterator iter;

for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {

int sum = num[i] + num[j];

iter = myMap.find(sum);

if(iter == myMap.end()) {
vector > newPair;
newPair.push_back(pair(i, j));
myMap[sum] = newPair;

} else {

(iter->second).push_back(pair(i, j));
}
}
}


for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {

int sum = target - num[i] - num[j];

iter = myMap.find(sum);

if(iter != myMap.end()) {

vector > pairs = iter->second;
int size = pairs.size();
for(int k = 0; k < size; k++) {

if(i > pairs[k].second) {

vector entry;

entry.push_back(num[i]);
entry.push_back(num[j]);
entry.push_back(num[pairs[k].first]);
entry.push_back(num[pairs[k].second]);
sort(entry.begin(), entry.end());

results.push_back(entry);
}
}
}
}
}

return results;
}
};
g***j
发帖数: 1275
2
大家别讨论无聊的话题了,帮我看看程序呀

【在 g***j 的大作中提到】
: 基本思路就是,先把两个的和存起来,并且把相应的index pair存到对应的直的map里
: 面去。
: 然后再把所有的两个的和和target的差算出来,去map里面找,因为map里面同样保存了
: 签名的数字的index,所以,只要后面两个数的最小的index比已有的最大的index大的
: 时候,就能保证不重复了。
: 可惜small set 15个总有一个不过,而且,因为显示问题,看不到哪个不过。哪个大侠
: 帮我看看代码?
: class Solution {
: public:
: vector > fourSum(vector &num, int target) {

g***j
发帖数: 1275
3
知道哪儿错了,因为保证index不重复,不能保证数字的结果不重复!
比如{0,0,0,0,0},target 0 就错了,回出现都是{0,0,0,0}的情况

【在 g***j 的大作中提到】
: 基本思路就是,先把两个的和存起来,并且把相应的index pair存到对应的直的map里
: 面去。
: 然后再把所有的两个的和和target的差算出来,去map里面找,因为map里面同样保存了
: 签名的数字的index,所以,只要后面两个数的最小的index比已有的最大的index大的
: 时候,就能保证不重复了。
: 可惜small set 15个总有一个不过,而且,因为显示问题,看不到哪个不过。哪个大侠
: 帮我看看代码?
: class Solution {
: public:
: vector > fourSum(vector &num, int target) {

d**e
发帖数: 6098
4
你的code应该可以更简洁一些。
第二个for i/j loop可以不要,直接loop map里面的元素就可以了

【在 g***j 的大作中提到】
: 知道哪儿错了,因为保证index不重复,不能保证数字的结果不重复!
: 比如{0,0,0,0,0},target 0 就错了,回出现都是{0,0,0,0}的情况

1 (共1页)
进入JobHunting版参与讨论
相关主题
给定一个值和sorted队列,找到所有pair(其和等于给定值)C++高手看下这个LC的LRU Cache的实现
Amazon first round phone interviewTwo problems from Google
C++ STL好像没有hashtable,大家需要的时候咋弄的?报个G的电面
讨论一道面试题写的LRU通不过大数据,帮忙看看
关于priority_queue一问请问下leetcode的two sum题目
Facebook Phone InterviewL的onsite冤了
Max Points on a Line 用c++map老是没法compile问surrounded region
问一下careercup一道题另开一贴unordered_set 对于 vector 和 pair 的has
相关话题的讨论汇总
话题: int话题: vector话题: num话题: iter话题: pair