LC 560. 和为K的子数组

思路:

• 分析题目
• 要找的是子数组的和==K的数量
• 子数组的和恰好可以利用前缀和来求
• 即找sum[r] == sum[l-1]+k的数量
• 我们用一个sum来存储i的前缀和
• 用一个HashMap来存储sum以及sum出现的次数
• 每次计算一个新的前缀和 ans += map.getOrDefault(sum-k,0)
• 注意初始化map.put(0,1)–>前缀和为0的次数为1

时间复杂度 O(N)

/**
* 求子数组的和->前缀和sum[r]-sum[l-1]
* 即求sum[r] = sum[l-1]+k就是子数组和为K的
*/
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int sum = 0;
        int ans = 0;
        //{key}->前缀和 {value}-->这个前缀和出现的次数
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        for(int i = 0 ; i < n ; i++){
            sum += nums[i];
            ans += map.getOrDefault(sum - k,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ans;
    }
}

LC.974和可被K整除的子数组

思路

• 与上题相同
• (sum[r] - sum[l-1]) % k = 0
• sum[r] % k == sum[l-1] % k

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int n = A.length;
        int sum = 0;
        int ans = 0;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        for(int item : A){
            sum = (sum + item % K + K) % K;
            ans += map.getOrDefault(sum,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ans;
    }
}