• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

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

    给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

    二、解题思路

    记录每一个位置的sum,存入HashMap中,如果某一个sum已经出现过,那么说明中间的subarray的sum为0. 时间复杂度O(n),空间复杂度O(n)

    三、解题代码

    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. int len = nums.length;
    10. ArrayList<Integer> ans = new ArrayList<Integer>();
    11. HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    12. map.put(0, -1);
    13. int sum = 0;
    14. for (int i = 0; i < len; i++) {
    15. sum += nums[i];
    16. if (map.containsKey(sum)) {
    17. ans.add(map.get(sum) + 1);
    18. ans.add(i);
    19. return ans;
    20. }
    21. map.put(sum, i);
    22. }
    23. return ans;
    24. }
    25. }