前缀和

preSum[i]为nums[0..i-1]的和
preSum[j+1]-preSum[i]为nums[i..j]的和
preSum + HashMap

1.中心数组下标

给你一个整数数组 nums ，请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        //前缀和 preSum[i] -> nums[0 -> i -1] 的和
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        for(int i = 0; i < n ; i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }
        for(int i = 0 ; i < n ; i++){
            if(preSum[i] == preSum[n] - preSum[ i + 1]){
                return i;
            }
        }
        return -1;
    }
}

2.和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 leetcode 560

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums.length == 0) {  return 0; }          
        HashMap<Integer,Integer> map = new HashMap<>();    
        map.put(0, 1);  //细节，这里需要预存前缀和为 0 的情况，会漏掉前几位就满足的情况
        int res = 0;
        int presum = 0;
        for (int x : nums) {
            presum += x;
            //当前前缀和已知，判断是否含有 presum - k的前缀和，那么我们就知道某一区间的和为 k 了。
            if (map.containsKey(presum - k)) {
                res += map.get(presum - k);//获取次数
            }
            //更新
            map.put(presum,map.getOrDefault(presum,0) + 1);
        }
        return res;
    }
}

3.优美子数组

给你一个整数数组 nums 和一个整数 k。 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 请返回这个数组中「优美子数组」的数目。 leetcode 1248

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        if (nums.length == 0) {  return 0; }   
        HashMap<Integer,Integer> map = new HashMap<>();
        //统计奇数个数，相当于我们的 presum
        int oddnum = 0;
        int count = 0;
        map.put(0,1);
        for (int x : nums) {
            // 统计奇数个数
            oddnum += x & 1;
            // 发现存在，则 count增加
            if (map.containsKey(oddnum - k)) {
             count += map.get(oddnum - k);
            }
            //存入
            map.put(oddnum,map.getOrDefault(oddnum,0)+1);
        }
        return count;
    }
}