《算法零基础100讲》(第60讲) 前缀和(四) 线性前缀和配合哈希表

《算法零基础100讲》(第60讲) 前缀和(四) 线性前缀和配合哈希表

1.1590. 使数组和能被 P 整除

class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int m = 0;
        for (int x : nums) {
            m = (m + x) % p; //得到所需的元素和
        }
        if(m == 0) {
            return 0;
        }
        int sum = 0, res = n;
        HashMap map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < n; i ++) {
            sum = (sum + nums[i]) % p; //得到的和
            int q = (sum - m + p) % p; //
            if(map.containsKey(q)) {
                res = Math.min(res, i - map.get(q));
            }
            map.put(sum, i);
        }
        return res == n ? -1 : res; //
    }
}

2.974. 和可被 K 整除的子数组

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        HashMap record = new HashMap();
        record.put(0,1);
        int sum = 0, ans = 0;
        for (int num : nums) {
            sum += num;
            int m = (sum % k + k) % k;//得到满足的数组
            int same = record.getOrDefault(m, 0);//统计符合的数组的子数组...
            ans += same;//计数所得符合的数组
            record.put(m, same + 1);
        }
        return ans;
    }
}

3.剑指 Offer II 011. 0 和 1 个数相同的子数组

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length, sum = 0, res = 0;
        HashMap map = new HashMap<>();
        //和为0的时候下标为-1
        map.put(0, -1);
        for(int i = 0; i < n; i++) {
            if(nums[i] == 0) {
                sum -= 1;
            }else {
                sum += 1;
            }
            if(map.containsKey(sum)) {
                res = Math.max(res, i - map.get(sum));
            }else {
                map.put(sum, i);
            }
        }
        return res;
    }
}

4.525. 连续数组

class Solution {
    public int findMaxLength(int[] nums) {
        int res = 0, sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                nums[i] = -1;//诺不存在的就返回-1
            }
        }
        HashMap  map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(sum == 0 && i > res) {//找到的含有连续相同的0,1子数组
                res = i + 1;
            } 
            if(map.containsKey(sum)) {
                res = Math.max(i - map.get(sum), res);//返回连续相同0,1子数组的长度最大值
            }else {
                map.put(sum, i);
            }
        }
        return res;
    }
}