Lintcode: Subarray Sum

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].

推荐解法：The idea is based on the prefix sum: Iterate through the array and for every element array【i】, calculate sum of elements form 0 to i (this can simply be done as sum += arr【i】). If the current sum has been seen before, then there is a zero sum array, the start and end index are returned.

用HashMap: O(N)时间，但是more memory, 大case会MLE

 1 public class Solution {
 2     /**
 3      * @param nums: A list of integers
 4      * @return: A list of integers includes the index of the first number 
 5      *          and the index of the last number
 6      */
 7     public ArrayList<Integer> subarraySum(int[] nums) {
 8         // write your code here
 9         ArrayList<Integer> res = new ArrayList<Integer>();
10         if (nums==null || nums.length==0) return res;
11         HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
12         map.put(0, -1);
13         int sum = 0;
14         for (int i=0; i<nums.length; i++) {
15             sum += nums[i];
16             if (!map.containsKey(sum)) {
17                 map.put(sum, i);
18             }
19             else {
20                 res.add(map.get(sum)+1);
21                 res.add(i);
22                 return res;
23             }
24         }
25         return res;
26     }
27 }

因为上面这个简洁的代码会MLE，所以(nlog(n))第二个算法，时间多一点，但是空间少一点

 1 class Element implements Comparable<Element>{
 2     int index;
 3     int value;
 4     public Element(int i, int v){
 5         index = i;
 6         value = v;
 7     }
 8     public int compareTo(Element other){
 9         return this.value-other.value;
10     }
11     public int getIndex(){
12         return index;
13     }
14     public int getValue(){
15         return value;
16     }
17 }
18 
19 public class Solution {
20     /**
21      * @param nums: A list of integers
22      * @return: A list of integers includes the index of the first number
23      *          and the index of the last number
24      */
25     public ArrayList<Integer> subarraySum(int[] nums) {
26         ArrayList<Integer> res = new ArrayList<Integer>();
27         if (nums==null || nums.length==0) return res;
28         int len = nums.length;
29         Element[] sums = new Element[len+1];
30         sums[0] = new Element(-1,0);
31         int sum = 0;
32         for (int i=0;i<len;i++){
33             sum += nums[i];
34             sums[i+1] = new Element(i,sum);
35         }
36         Arrays.sort(sums);
37         for (int i=0;i<len;i++)
38             if (sums[i].getValue()==sums[i+1].getValue()){
39                 int start = Math.min(sums[i].getIndex(),sums[i+1].getIndex())+1;
40                 int end = Math.max(sums[i].getIndex(),sums[i+1].getIndex());
41                 res.add(start);
42                 res.add(end);
43                 return res;
44             }
45 
46         return res;
47     }
48 }