你的位置:首页 > Java教程

[Java教程]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.ExampleGiven [-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 integers22    * @return: A list of integers includes the index of the first number23    *     and the index of the last number24   */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 }