g***j
发帖数: 1275 | 1 给一个int数组, 求出所有和为0的子数组？ 怎么求？
最优化的算法是什么？ | p*****2
发帖数: 21240 | 2
DFS+剪枝？
【在 g***j 的大作中提到】
: 给一个int数组, 求出所有和为0的子数组？ 怎么求？
: 最优化的算法是什么？
| w****x
发帖数: 2483 | 3 b[i] = a[0] + ... + a[i]
扫描b加hash_map查相同的数 | f*****e
发帖数: 2992 | 4 位置不一定连续。
【在 w****x 的大作中提到】
: b[i] = a[0] + ... + a[i]
: 扫描b加hash_map查相同的数
| d****n
发帖数: 233 | 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;
} | h*******e
发帖数: 1377 | | h*****3
发帖数: 1391 | 7 Re。
求subset，然后算每个subset的sum，肯定可以。不过不知道是不是最优。
【在 h*******e 的大作中提到】
: 子集合数吧。。dp或者搜索。
|
|
