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或者搜索。
相关阅读
Nvidia Sr/Lead SW Engineer job openings说我特别喜欢的一个人物，骆家辉。是不是自己当老板比打工容易呢embedded software engineer 如何转纯软?FDA ORISE Fellow vs. CRO PM这个板叫jobhunting, 有没有一个版叫atwork啊AMP Job Description SW Engineer LeaderWework NYC offer如果让你重新选择 你会选什么专业少壮不刷题，老大徒伤悲旧时王谢堂前燕，飞入寻常百姓家。为什么说投行的IT是笑话？是很简单么？刷题就是给人打工的思路每天一发。我们的目标是用刷题绑架所有公司的招聘谁说前端简单的 我宁愿刷题如果老板嫉妒你，如何解？中午又要去吃QQ Noodle 了 算不算打广告google maps好牛啊linux下， 一个thread 正在写文件，如果另一个thread试图去删去 (转载)生活不只有眼前的POJ 还有诗和远方