f**********t
发帖数: 1001 | 1 这题应该不难，以前还做过，但是就是不能全pass。。。
我的思路是这样的，外面是一个二重循环，i从0到n - 2, j 从i+1到n-1。然后里面也
有个二重循环，把所有小于i的两个数的加和都存进去。
不知我的代码哪里有不对？或者谁能提供一个正确的版本给我看看。。。多谢！:)
这是我的代码：
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > result;
map > mp;
set > resultset;
sort(num.begin(), num.end());
for (int i = 0; i < (int)num.size() - 1; ++i) {
for (int j = i + 1; j < (int)num.size(); ++j) {
int val = target - num[i] - num[j];
if (mp.find(val) != mp.end()) {
vector tmpvec;
tmpvec.push_back(mp[val].first);
tmpvec.push_back(mp[val].second);
tmpvec.push_back(num[i]);
tmpvec.push_back(num[j]);
if (resultset.find(tmpvec) == resultset.end()) {
result.push_back(tmpvec);
resultset.insert(tmpvec);
}
}
}
// 把i之前的数的两两加和hash
for (int k = 0; k <= i - 1; ++k) {
for (int l = k + 1; l <= i; ++l) {
mp[num[k] + num[l]] = make_pair(num[k], num[l]);
}
}
}
return result;
} | r******g
发帖数: 13 | 2 O(n^3),
Run Status: Accepted!
Program Runtime: 8 milli secs
Progress: 15/15 test cases passed.
Run Status: Accepted!
Program Runtime: 336 milli secs
my hashtable solution O(n^2) exceeds memory limit, if anyone has code(O^2)
passing OJ, please let me know.
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > results;
int n = num.size();
if(n < 4) return results;
sort(num.begin(), num.end());
int temp = 0;
vector quad(4, 0);
int i = 0;
while(i< n-3) {
int j = i+1;
while(j < n-2) {
int p = j+1, q = n-1;
while(p< q) {
int sum = num[i]+num[j]+num[p] + num[q];
if(sum == target) {
quad[0] = num[i];
quad[1] = num[j];
quad[2] = num[p];
quad[3] = num[q];
results.push_back(quad);
while(p
while(p
}
else if(sum < target){
temp = num[p];
while(p
}
else {
temp = num[q];
while(p
}
}
temp = num[j];
while(j
}
temp = num[i];
while(i
}
return results;
}
}; | f**********t
发帖数: 1001 | 3 嗯，后来我又做出了O(n^2)。之前错误是因为没有考虑有多个解。
vector > fourSum(vector &num, int target) {
map > > mp; // mp存所有给定和为某整数的数对
set > uniqueset; // set，保存所有不重复的4元组
vector > ret;
sort(num.begin(), num.end());
for (int i = 0; i < (int)(num.size() - 1); ++i) {
for (int j = i + 1; j < num.size(); ++j) {
int currval = target - num[i] - num[j];
if (mp.find(currval) != mp.end()) {
for (int k = 0; k < mp[currval].size(); ++k) {
vector tmp;
tmp.push_back(mp[currval][k].
first);
tmp.push_back(mp[currval][k].second);
tmp.push_back(num[i]);
tmp.push_back(num[j]);
if (uniqueset.find(tmp) == uniqueset.end()) {
uniqueset.insert(tmp);
ret.push_back(tmp);
}
}
}
}
for (int k = 0; k < i; ++k)
mp[num[k] + num[i]].push_back(make_pair(num[k], num[i]));
}
return ret;
}
【在 r******g 的大作中提到】
: O(n^3),
: Run Status: Accepted!
: Program Runtime: 8 milli secs
: Progress: 15/15 test cases passed.
: Run Status: Accepted!
: Program Runtime: 336 milli secs
: my hashtable solution O(n^2) exceeds memory limit, if anyone has code(O^2)
: passing OJ, please let me know.
: class Solution {
: public:
| b****g
发帖数: 192 | 4 为了防止4元组重复，我没用set或者map保存整数对而是在每个for循环之后立即判断，
如果num[i] == num[i-1]，那么就重复了，于是就不执行底下的操作，直接++i了。这
样就不用uniqueset，比较省空间。看下面的注释
~~这里判断如果num[i] == num[i-1]，那么就重复了，于是continue;
~~这里判断如果num[j] == num[j]，就continue;
【在 f**********t 的大作中提到】
: 嗯，后来我又做出了O(n^2)。之前错误是因为没有考虑有多个解。
: vector > fourSum(vector &num, int target) {
: map > > mp; // mp存所有给定和为某整数的数对
: set > uniqueset; // set，保存所有不重复的4元组
: vector > ret;
: sort(num.begin(), num.end());
: for (int i = 0; i < (int)(num.size() - 1); ++i) {
: for (int j = i + 1; j < num.size(); ++j) {
: int currval = target - num[i] - num[j];
: if (mp.find(currval) != mp.end()) {
| b****g
发帖数: 192 | 5 可不可以试试在进入每个while循环之后立即判断，
如果num[i] == num[i-1]，那么就重复了，于是就不执行底下的操作，直接++i了。
我在楼上回复了这个方法。
【在 r******g 的大作中提到】
: O(n^3),
: Run Status: Accepted!
: Program Runtime: 8 milli secs
: Progress: 15/15 test cases passed.
: Run Status: Accepted!
: Program Runtime: 336 milli secs
: my hashtable solution O(n^2) exceeds memory limit, if anyone has code(O^2)
: passing OJ, please let me know.
: class Solution {
: public:
| r******g
发帖数: 13 | 6 It will ignore the quad containing num[i-1] and num[i], I find it's easier
to deal with it when you find a solution.
This O(n^2) solution without using set, both the (unordered_map) and results
(vector) doesn't contain duplicates by preprocessing the array.
Run Status: Accepted!
Program Runtime: 16 milli secs
Progress: 15/15 test cases passed.
Run Status: Accepted!
Program Runtime: 460 milli secs
Progress: 282/282 test cases passed.
Sorry can't type chinese, please feel free to comment my code, better to
make it more concise and efficient. My O(n2) solution takes longer than O(n3
), I can think it might relate to the cost of using unordered_map, but
shouldn't be still faster?
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > results;
int n = num.size();
if(n < 4) return results;
typedef pair sumPair;
typedef unordered_map > sumMap;
sumMap localMap;
vector quad(4, 0);
int temp = 0;
sort(num.begin(), num.end());
for(int i = 2; i
int q = i-1, p = 0;
if(q ==1 || num[q] != num[q-1])
{
while(p
int val = num[p] + num[q];
localMap[val].push_back(sumPair(num[p], num[q]));
temp = num[p];
while(p
}
}
else{
int val = num[q] + num[q-1];
if(localMap.find(val) ==localMap.end())
localMap[val].push_back(sumPair(num[q], num[q]));
else{
int k = 0;
for(; k
if(localMap[val][k].first == num[q]) break;
if(k==localMap[val].size())
localMap[val].push_back(sumPair(num[q], num[q]));
}
}
for(int j = i+1; j
int val = target - num[i] - num[j];
sumMap::const_iterator it = localMap.find(val);
if(it != localMap.end()){
for(int t = 0; t < localMap[val].size(); ++t){
quad[0] = localMap[val][t].first;
quad[1] = localMap[val][t].second;
quad[2] = num[i];
quad[3] = num[j];
int oldI = i; temp = num[i];
while(oldI>= 0 && num[--oldI] == temp);
if(num[i] != num[i-1] ||(i-oldI==2 && quad[1] == num[i-1])
||(i-oldI ==3 && quad[0] == quad[1] &&quad[1]==num[i]))
//~~~ deal with repeated numbers
results.push_back(quad);
}
}
temp = num[j];
while(j
}
}
return results;
}
【在 b****g 的大作中提到】
: 可不可以试试在进入每个while循环之后立即判断，
: 如果num[i] == num[i-1]，那么就重复了，于是就不执行底下的操作，直接++i了。
: 我在楼上回复了这个方法。
|
|
