Prefix Sum&&HashMap

560. Subarray Sum Equals K

不关心具体是哪两项的前缀和之差等于k，只关心等于 k 的前缀和之差出现的次数c，就知道了有c个子数组求和等于k

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n=nums.length;
        int count=0;
        int sum=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        for(int i=0; i<n; i++){
            sum+=nums[i];
            if(map.containsKey(sum-k)){
                count+=map.get(sum-k);
            }
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;
    }
}

1248. Count Number of Nice Subarrays

奇数个数为 k 的区间数量, 等价于在对区间各项 &1 后，和为 k 的区间数量

public class LeetCode1248 {
    public int numberOfSubarrays(int[] nums, int k) {
        int count=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        int n=nums.length;
        int sum=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i]&1;
            if(map.containsKey(sum-k)){
                count+=map.get(sum-k);
            }
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;
    }
}

974. Subarray Sums Divisible by K

注意：mod后可能是 (-k,k) 间的任意值，需要处理，且不可以通过定长数组来优化

Java负数参与的取模运算规则：

先忽略负号，按照正数运算之后，被取模的数是正数结果就取正，反之取负。

即只看被除的数7的符号，不考虑除数3的符号！！！

public class LeetCode974 {
    public int subarraysDivByK(int[] nums, int k) {
        int n=nums.length;
        int count=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        int sum=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            int mod=(sum%k+k)%k;
            if(map.containsKey(mod)){
                count+=map.get(mod);
            }
            map.put(mod,map.getOrDefault(mod,0)+1);
        }
        return count;
    }
}

523. Continuous Subarray Sum

map中记录之前最早的 sum%k 后结果为 mod 的区间的终点

若再找到一个相同的 mod 且间隔大于 2，则满足

public class LeetCode523 {
    public boolean checkSubarraySum(int[] nums, int k) {
        int sum=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,-1);
        int n=nums.length;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
            int mod=sum%k;
            if(map.containsKey(mod)){
                if(i-map.get(mod)>=2){
                    return true;
                }
                continue;
            }
            map.put(mod,i);
        }
        return false;
    }
}

525. Contiguous Array

public int findMaxLength(int[] nums) {
    int n=nums.length;
    Map<Integer,Integer> map=new HashMap<>();
    map.put(0,-1);
    int sum=0;
    int res=0;
    for (int i = 0; i < n; i++) {
        sum+=nums[i]==0 ? -1 :1;
        if(map.containsKey(sum)){
            //[0,i]
            //[0,val]
            //[val+1,i] = 0
            res=Math.max(res,i-map.get(sum));
        }else{
            map.put(sum,i);
        }
    }
    return res;
}

2731. Movement of Robots

经典新题：新瓶装老酒

• 新瓶：理解情境，转化题意，化繁为简！
• 老酒：prefix sum求difference
• edge case: 注意overflow

public int sumDistance(int[] nums, String s, int d) {
    //collision won't change positions
    int n=nums.length;
    long[] arr=new long[n];
    for (int i = 0; i < n; i++) {
        if(s.charAt(i)=='R'){
            arr[i]=nums[i]+d;
        }else{
            arr[i]=nums[i]-d;
        }
    }
    Arrays.sort(arr);
    long[] sum=new long[n+1]; //[0,i-1]
    int mod=(int)1e9+7;
    for (int i = 0; i < n; i++) {
        sum[i+1]=sum[i]+arr[i];

    }
    long res=0;
    for (int i = 0; i < n; i++) {
        //only consider one side to avoid duplication
        //left side: [0,i-1] = sum[i]
        //right side: [i+1,n-1] = sum[n] - sum[i+1]
        res+=(arr[i]*i - sum[i])%mod;
        res%=mod;
    }
    return (int)res;
}