子数组之和＝0

［抄题］：

给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置.给出 [-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].

［思维问题］：

老是想着数组双重循环用枚举法，想不到任何别的数据结构。

用hashmap的好处：一个数据结构可以包括两个变量，index及其sum。两个变量都要处理时，用hashmap。

利用哈希图的index的唯一性，可以检测sum是不是重复，间接判断和是否为零。（上次是利用index的唯一性，每次都在value上减100，从而统计重复出现的次数。）

［一句话思路］：

用index来存和，如果index重复，则和为零。

［画图］：

［一刷］：

找到后还必须添加到hashmap中，继续找。
ArrayList<Integer> ans = new ArrayList<Integer>();尖括号里是数据类型，要写integer。接口和数据类型一样，免得麻烦。数据类型都是大写开头。
map对应的是put函数。
list类型的函数必须要return东西，return ans结果list就行。
for(int i = 0; i < nums.length; i++)，不用减一！！

［总结］：

［复杂度］：

n/n

［英文数据结构］：

用hashmap的好处：一个数据结构可以包括两个变量，index及其sum。两个变量都要处理时，用hashmap。

返回array不行：必须初始化，但是初始化哪一位都不一定求和为0。利用arraylist不用初始化的优点，找到一个是一个，动态添加。

［其他解法］：

［题目变变变］：

closest，定义了一个结构体，没看懂

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 List<Integer> subarraySum(int[] nums) {
        // write your code here
        if (nums.length == 0 || nums == null) {
            return null;
        }
        
        int sum = 0;
        ArrayList<Integer> ans = new ArrayList<Integer>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        map.put(0, -1);
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                ans.add(map.get(sum) + 1);
                ans.add(i);
                
                return ans;
            }
            map.put(sum,i);
        }
        return ans;
    }
}

View Code