具有严格记忆限制的O(n^3)中5 5SUM的求解
我需要一种方法来解决经典的5 5SUM问题，没有散列或内存高效的方式哈希。
这个问题要求你找出给定长度N的数组中有多少个子序列的和等于S。
例如：
Input
6 5
1 1 1 1 1 1
Output
6这些限制是：
N <= 1000 ( size of the array )
S <= 400000000 ( the sum of the subsequence )
Memory usage <= 5555 kbs
Execution time 2.2s我很确定例外的复杂性是O(N^3)。由于内存限制，散列不能提供实际的O(1)时间。
我得到的最好结果是用这段代码得到70分。(我在6次考试中得了TLE )
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define MAX 1003
#define MOD 10472
using namespace std;
ifstream in("take5.in");
ofstream out("take5.out");
vector<pair<int, int>> has[MOD];
int v[MAX];
int pnt;
vector<pair<int, int>>::iterator it;
inline void ins(int val) {
pnt = val%MOD;
it = lower_bound(has[pnt].begin(), has[pnt].end(), make_pair(val, -1));
if(it == has[pnt].end() || it->first != val) {
has[pnt].push_back({val, 1});
sort(has[pnt].begin(), has[pnt].end());
return;
}
it->second++;
}
inline int get(int val) {
pnt = val%MOD;
it = lower_bound(has[pnt].begin(), has[pnt].end(), make_pair(val, -1));
if(it == has[pnt].end() || it->first != val)
return 0;
return it->second;
}
int main() {
int n,S;
int ach = 0;
int am = 0;
int rez = 0;
in >> n >> S;
for(int i = 1; i <= n; i++)
in >> v[i];
sort(v+1, v+n+1);
for(int i = n; i >= 1; i--) {
if(v[i] > S)
continue;
for(int j = i+1; j <= n; j++) {
if(v[i]+v[j] > S)
break;
ins(v[i]+v[j]);
}
int I = i-1;
if(S-v[I] < 0)
continue;
for(int j = 1; j <= I-1; j++) {
if(S-v[I]-v[j] < 0)
break;
for(int k = 1; k <= j-1; k++) {
if(S-v[I]-v[j]-v[k] < 0)
break;
ach = S-v[I]-v[j]-v[k];
rez += get(ach);
}
}
}
out << rez << '\n';
return 0;
}回答 1
Stack Overflow用户
发布于 2016-05-07 00:11:36
我认为这是可以做到的。我们正在寻找数组arr中5项的所有子集和正确的SUM。我们有带有索引0..N-1的数组。这五项中的第三项可以在范围i中使用索引2..N-3。我们循环所有这些指数。对于每个索引i，我们生成索引范围内的所有两个数字的组合，0..i-1在索引i的左边，以及在索引i右侧的范围i+1..N-1中，所有两个数字的组合。对于每一个索引i，左侧的N*N组合都小于右侧。我们只存储每个组合的和，所以它不会超过1000 * 1000 *4= 4MB。
现在我们有两个数字序列(和)，任务是:从第一序列取一个数，从第二序列取一个数，得到等于Si = SUM - arr[i]的和。有多少种组合？为了有效地完成这一任务，必须对序列进行排序。假设先排序升序，并有数字a, a, a, b, c ,...。第二种是降序排序，并有数字Z, Z, Y, X, W, ...。如果是a + Z > Si，那么我们可以丢弃Z，因为我们没有更小的数字可匹配。如果a + Z < Si，我们可以丢弃a，因为我们没有更大的数字可匹配。如果是a + Z = Si，我们有2*3=6个新的组合，并且去掉了a和Z。如果我们得到免费排序，它是很好的O(N^3)算法。
排序不是免费的，而是O(N * N^2 * log(N^2)) = O(N^3 * log(N))。我们需要在线性时间进行排序，这是不可能的。还是真的是这样？在索引i+1中，我们可以重用索引i中的序列。i+1的新组合很少--只有那些涉及数字arr[i]和索引0..i-1中的一些数字的组合。如果我们对它们进行排序(而且我们可以，因为没有它们的N*N，但最多只有N )，那么我们所需要的就是合并两个排序的序列。这可以在线性时间内完成。如果在开始时对arr进行排序，甚至可以避免完全排序。我们只是合并。
对于第二个序列，合并不涉及添加而是删除，但它非常简单。
该实现似乎有效，但我希望在某个地方出现一个错误；)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int Generate(int arr[], int i, int sums[], int N, int NN)
{
int p1 = 0;
for (int i1 = 0; i1 < i - 1; ++i1)
{
int ai = arr[i1];
for (int i2 = i1 + 1; i2 < i; ++i2)
{
sums[p1++] = ai + arr[i2];
}
}
sort(sums, sums + p1);
return p1;
}
int Combinations(int n, int sums[], int p1, int p2, int NN)
{
int cnt = 0;
int a = 0;
int b = NN - p2;
do
{
int state = sums[a] + sums[b] - n;
if (state > 0) { ++b; }
else if (state < 0) { ++a; }
else
{
int cnta = 0;
int lastA = sums[a];
while (a < p1 && sums[a] == lastA) { a++; cnta++; }
int cntb = 0;
int lastB = sums[b];
while (b < NN && sums[b] == lastB) { b++; cntb++; }
cnt += cnta * cntb;
}
} while (b < NN && a < p1);
return cnt;
}
int Add(int arr[], int i, int sums[], int p2, int N, int NN)
{
int ii = N - 1;
int n = arr[i];
int nn = n + arr[ii--];
int ip = NN - p2;
int newP2 = p2 + N - i - 1;
for (int p = NN - newP2; p < NN; ++p)
{
if (ip < NN && (ii < i || sums[ip] > nn))
{
sums[p] = sums[ip++];
}
else
{
sums[p] = nn;
nn = n + arr[ii--];
}
}
return newP2;
}
int Remove(int arr[], int i, int sums[], int p1)
{
int ii = 0;
int n = arr[i];
int nn = n + arr[ii++];
int pp = 0;
int p = 0;
for (; p < p1 - i; ++p)
{
while (ii <= i && sums[pp] == nn)
{
++pp;
nn = n + arr[ii++];
}
sums[p] = sums[pp++];
}
return p;
}
int main() {
ifstream in("take5.in");
ofstream out("take5.out");
int N, SUM;
in >> N >> SUM;
int* arr = new int[N];
for (int i = 0; i < N; i++)
in >> arr[i];
sort(arr, arr + N);
int NN = (N - 3) * (N - 4) / 2 + 1;
int* sums = new int[NN];
int combinations = 0;
int p1 = 0;
int p2 = 1;
for (int i = N - 3; i >= 2; --i)
{
if (p1 == 0)
{
p1 = Generate(arr, i, sums, N, NN);
sums[NN - 1] = arr[N - 1] + arr[N - 2];
}
else
{
p1 = Remove(arr, i, sums, p1);
p2 = Add(arr, i + 1, sums, p2, N, NN);
}
combinations += Combinations(SUM - arr[i], sums, p1, p2, NN);
}
out << combinations << '\n';
return 0;
}https://stackoverflow.com/questions/37027336
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号