哈希集合应用

1.中心索引
//左侧所有元素相加的和等于右侧所有元素相加的和。

class Solution {
    public int pivotIndex(int[] nums) {
        int presum = 0;
        //数组的和
        for (int x : nums) {
           presum += x;
        }      
        int leftsum = 0;
        for (int i = 0; i < nums.length; ++i) {
            //发现相同情况
            if (leftsum == presum - nums[i] - leftsum) {
                return i;
            }
            leftsum += nums[i];          
        }
        return -1;
    }
}

2两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer,Integer> map  = new HashMap<>();
        //一次遍历
        for (int i = 0; i < nums.length; ++i) {
            //存在时，我们用数组得值为 key，索引为 value
            if (map.containsKey(target - nums[i])){              
               return new int[]{i,map.get(target-nums[i])};
            }
            //存入值
            map.put(nums[i],i);
        }
        //返回
        return new int[]{};
    }
}

3.和为k的子数组的个数

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);//
        int count = 0;
        int presum = 0;
        for (int x : nums) {
            presum += x;
            //当前前缀和已知，判断是否含有 presum - k的前缀和，那么我们就知道某一区间的和为 k 了。
            if (map.containsKey(presum - k)) {
                count += map.get(presum - k);//获取次数
            }
            //更新
            map.put(presum,map.getOrDefault(presum,0) + 1);
        }
        return count;
    }
}

4优美子数组
// 连续 子数组中恰好有 k 个奇数数字

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;
    }
}

5.和可被k整除

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int presum = 0;
        int count = 0;
        for (int x : A) {
             presum += x;
             //当前 presum 与 K的关系，余数是几，当被除数为负数时取模结果为负数，需要纠正
             int key = (presum % K + K) % K;
             //查询哈希表获取之前key也就是余数的次数
             if (map.containsKey(key)) {
                 count += map.get(key);
             }
             //存入哈希表当前key，也就是余数
             map.put(key,map.getOrDefault(key,0)+1);
        }
        return count;
    }
}

6.连续子数组和
含有连续的子数组，其大小至少为 2，且总和为 k 的倍数

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        //细节2
        map.put(0,-1);
        int presum = 0;
        for (int i = 0; i < nums.length; ++i) {
            presum += nums[i];
            //细节1，防止 k 为 0 的情况
            int key = k == 0 ? presum : presum % k;
            if (map.containsKey(key)) {
                if (i - map.get(key) >= 2) {
                     return true;
                }
                //因为我们需要保存最小索引，当已经存在时则不用再次存入，不然会更新索引值
                continue;           
            } 
            map.put(key,i);                  
        }
        return false;
    }
}