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.
考点是前缀和。
Solution 1: faster, uses more space.

public class Solution {
    public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Map<Long, Integer> prefixSumMap = new HashMap<Long, Integer>();
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == 0) {
                res.add(0);
                res.add(i);
                break;
            }
            if (prefixSumMap.containsKey(sum)) {
                res.add(prefixSumMap.get(sum)+1);
                res.add(i);
                break;
            } else {
                prefixSumMap.put(sum, i);
            }
        }
        return res;
    }
}

Solution 2: slower, uses less space

public class Solution {
    class Element implements Comparable<Element>{
      private int index;
      private int val;

      Element (int index, int val) {
        this.index = index;
        this.val = val;
      }

      public int getVal() {
        return val;
      }

      public int getIndex() {
        return index;
      }

      public int compareTo(Element e) {
        return val - e.getVal();
      }
    }

    public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
          return res;
        }
        int sum = 0;
        Element[] eles = new Element[nums.length];
        for (int i = 0; i < nums.length; i++) {
          sum += nums[i];
          eles[i] = new Element(i, sum);
        }
        Arrays.sort(eles);
        for (int i = 0; i < eles.length; i++) {
          if (eles[i].getVal() == 0) {
            res.add(0);
            res.add(eles[i].getIndex());
            break;
          }
          if (i > 0 && eles[i].getVal() == eles[i-1].getVal()) {
            res.add(eles[i].getIndex());
            res.add(eles[i-1].getIndex());
            break;
          }
        }
        return res;
    }
}