A**u
发帖数: 2458 | 1 数组A[1,n]
找出 index a,b 使得 A[a]+A[a+1]+...+A[b] = 0;
多谢 | u***q
发帖数: 21 | 2 assume for any 1 <= i <= j <=n, A[i]+A[i+1]+...+A[j] is not go beyond INT_
MIN or INT_MAX.
HashTable ht;
int a = -1, b = -1;
int sum = 0;
int i;
for (i = 1;i <=n; i++) {
sum += A[i];
if (sum == 0) {
a = 1;
b = i;
break;
}
if (ht.has(sum)) {
a = ht.get(sum) + 1;
b = i;
break;
}
ht.add(sum, i);
} |
|
