Lintcode: Subarray Sum - neverlandly - 博客园

Lintcode: Subarray Sum - neverlandly - 博客园

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 subarraySum(int[] nums) { 8 // write your code here 9 ArrayList res = new ArrayList(); 10 if (nums==null || nums.length==0) return res; 11 HashMap map = new HashMap();

Read full article from Lintcode: Subarray Sum - neverlandly - 博客园