p*2
2 楼
DFS+剪枝？
【在 g***j 的大作中提到】
: 给一个int数组, 求出所有和为0的子数组？ 怎么求？
: 最优化的算法是什么？
w*x
3 楼
b[i] = a[0] + ... + a[i]
扫描b加hash_map查相同的数
扫描b加hash_map查相同的数
f*e
4 楼
位置不一定连续。
【在 w****x 的大作中提到】
: b[i] = a[0] + ... + a[i]
: 扫描b加hash_map查相同的数
【在 w****x 的大作中提到】
: b[i] = a[0] + ... + a[i]
: 扫描b加hash_map查相同的数
d*n
5 楼
vector subsets(vector a) {
int n = a.size();
// minimum negative sum
int min = 0;
// max postive sum
int max = 0;
for(int i = 0; i < n; i++) {
if (a[i] < 0) {
min += a[i];
}
else {
max += a[i];
}
// mask[i] = 1 means there is a sub sum equals to i
int mask[] = new int[-min + max + 1];
// lookupTable[i, j] = 1 means there is a sub sum equals to j
// and a[i] is in the sub set
vector> lookupTable(n, -min + max +1);
for( int i = 0; i < n; ++i) {
lookupTable[i][a[i]-min] = 1;
mask[a[i]-min] = 1;
for(int j= 1; i + j < n; ++j) {
for (int k = math.min(0, -a[j]); k < max + 1 -min; ++k) {
if (mask[k]) {
mask[k+a[j] = 1;
lookupTable[j][k+a[j] = 1;
}
}
}
}
vector output;
output.push_back(subsets(mask, lookupTable, 0));
for(int i = 1; i < math.min(max, -min); i++) {
if (mask[i - min] == 1 && mask[-i - min] == 1) {
foreach(vector sub in outer_join(subsets(mask, lookupTable,
i), subsets(mask, lookupTable, -i))) {
output.push_back(sub);
}
}
}
return output;
}
vector> subsets(vector mask, vector>lookupTable
, int target) {
return all subsets which sum to target;
}
int n = a.size();
// minimum negative sum
int min = 0;
// max postive sum
int max = 0;
for(int i = 0; i < n; i++) {
if (a[i] < 0) {
min += a[i];
}
else {
max += a[i];
}
// mask[i] = 1 means there is a sub sum equals to i
int mask[] = new int[-min + max + 1];
// lookupTable[i, j] = 1 means there is a sub sum equals to j
// and a[i] is in the sub set
vector
for( int i = 0; i < n; ++i) {
lookupTable[i][a[i]-min] = 1;
mask[a[i]-min] = 1;
for(int j= 1; i + j < n; ++j) {
for (int k = math.min(0, -a[j]); k < max + 1 -min; ++k) {
if (mask[k]) {
mask[k+a[j] = 1;
lookupTable[j][k+a[j] = 1;
}
}
}
}
vector
output.push_back(subsets(mask, lookupTable, 0));
for(int i = 1; i < math.min(max, -min); i++) {
if (mask[i - min] == 1 && mask[-i - min] == 1) {
foreach(vector
i), subsets(mask, lookupTable, -i))) {
output.push_back(sub);
}
}
}
return output;
}
vector
, int target) {
return all subsets which sum to target;
}
h*e
6 楼
子集合数吧。。dp或者搜索。
h*3
7 楼
Re。
求subset，然后算每个subset的sum，肯定可以。不过不知道是不是最优。
【在 h*******e 的大作中提到】
: 子集合数吧。。dp或者搜索。
求subset，然后算每个subset的sum，肯定可以。不过不知道是不是最优。
【在 h*******e 的大作中提到】
: 子集合数吧。。dp或者搜索。
相关阅读
紧急求助！！！！！！要被学校dismiss了，该选主动withdraw吗请问电面后要推荐信和成绩单杯具的h1b申请，大家来帮我看一下FB interview questionH1b转F1的问题Sr. Talent Acquisition Recruiter 第一轮onsite会问什么问题？Do quants get pussies? (转载)大家都是面了多少个电话面试和onsite以后拿到offer的？有人面过lab126么？opt期间没有update自己的情况，后果严重吗？Re: 【JOBS】06.01 -- 06.30 (转载)can PhD apply for a secretary job and getting H1B?跟一个小公司的senior president吃午饭google MTV给master+2 years experience的offer大概有多少？问一道题目急问：电脑硬盘坏了，有可能恢复硬盘里保持的数据吗？贴个FLEXTRADE的在线C++测试的题请问一个sql的问题Onsite选在2周后好不好？Urgent, how to negotiate my salary? (offer granted)