> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/presum/subarray_sum.md).

# Subarray Sum

**Easy** 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.

## Thoughts

傻办法需要三循环，$$O(n^3)$$。我们可以先存一个preSum数组，用来存储到从0到i-1时数组和是多少。那么为子数组为０相当于说preSum中两个成员的值相等，这两个值之所夹的子数组即所求。

## Code

```
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) {
        Map<Integer, Integer> preSum = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<>();
        preSum.put(0, -1); // to handle cases like [-1, 1]
        for (int i = 0, sum = 0; i < nums.length; i++) {
            sum += nums[i];
            if (preSum.containsKey(sum)) {
                res.add(preSum.get(sum) + 1);
                res.add(i);
                return res;
            } else {
                preSum.put(sum, i);
            }
        }

        return res;
    }
}
```

## Anlysis

TC: O(n)

SC: O(n)