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.
Have you met this question in a real interview?
Yes
Example
Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].
Note
There is at least one subarray that it's sum equals to zero.
Tags Expand
public class Solution { /** * @param nums: A list of integers * @return: A list of integers includes the index of the first number * and the index of the last number */ public ArrayList<Integer> subarraySum(int[] nums) { // write your code here ArrayList<Integer> list = new ArrayList<Integer>(); HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); int sum = 0; // We set the index -1 sum to be 0 to let us more convient to count. map.put(0,-1); for(int i = 0 ; i < nums.length ; i++){ sum += nums[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 list.add(map.get(sum) + 1); list.add(i); return list; } map.put(sum,i); } return list; } }