S*******C
发帖数: 822 | 1 Subarray Sum
20%
Accepted
Given an integer array, find a subarray where the sum of numbers is zero.
Your code should return the index of the first number and the index of the
last number.
Example
Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].
http://www.lintcode.com/en/problem/subarray-sum/
下面的解法总是在第16个test case Memory Limit Exceeded
public ArrayList subarraySum(int[] a) {
ArrayList res = new ArrayList();
//a map between sum and index
HashMap map = new HashMap();
// We set the index -1 sum to be 0 to let us more convenient to
count.
map.put(0, -1);
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
if (map.containsKey(sum)) {
// For example:
// -3 1 2 -3 4
// SUM: 0 -3 -2 0 -3 1
// then we got the solution is : 0 - 2
res.add(map.get(sum) + 1);
res.add(i);
return res;
}
// Store the key:value of sum:index.
map.put(sum, i);
}
return res;
} |
|
