拼多多2021 java后端实习生 笔试 前缀和优雅解决方案

拼多多2021笔试 前缀和优雅解决方案

直接给例子便于理解

给定一个数组例如{1，2，3，4，5} 求取余2的所有连续子序列个数 本例子答案是6 包含 [2],[4],[1,2,3],[1,2,3,4],[3,4,5],[2,3,4,5]总六种情况

import java.util.*;
public class Main{
          
   
    public static void main(String args[]){
          
   
        int A[]=new int[]{
          
   1,2,3,4,5};

        //先求出{1，2，3，4，5}取余2后的情况，结果为{1，0，1，0，1}
        for(int i=0;i<5;i++){
          
   
            A[i] = A[i] % 2;
        }

        //sum[i]即前i个value的和 取余2的值 结果为{1,1,0,0,1}
        int sum[]=new int[5];
        sum[0]=A[0]%2;
        for(int i=1;i<5;i++){
          
   
            sum[i] = (sum[i-1]+A[i])%2;
        }

        long count=0;
        HashMap<Integer,Integer> hashmap=new HashMap<>();
        hashmap.put(0,1);
        for(int i=0;i<5;i++){
          
   
            if(hashmap.containsKey(sum[i]))
                count+=hashmap.get(sum[i]); 
            //sum[]={1,1,0,0,1} 首先第一次进入for，由于hashmap里面没有key为1的值，所以不执行if，
            //执行hashmap.put(1,1),然后i++，此时sum[i]也即sum[1]=1，所以count+=1，
            //执行hashmap.put(1,1+1);   为什么要加1呢？？？  这里也即这种解法的优雅之处
            // 因为sum[0]=1,也就是说A[0]肯定是一个奇数（因为只有奇数取余2才会为奇数）
            //然后sum[1]=1,也就是(A[0]+A[1])%2==1,因为A[0]是奇数,所以A[1]必是一个可以被2整除取余结果为0的偶数
            //所以要执行hashmap.put(1,1+1); 因为这样子会把我其中一个情况 [2] 给忽略了，所以我要加1
            //以此类推，后面的都是这样，其实不管是取余2还是取余3都是通用的，例如取余3
            //sum[0]=1的话，sum[1]=A[0]+A[1]=1;那也要加1，因为假设A[1]=3，（A[0]+A[1]）%3==1
           //哪怕出现最特殊A[1]=0，那也是满足的，因为0%3==0,所以相应的在map中的key而要加上1（被忽略掉的某个满足条件的子集）
            hashmap.put(sum[i],hashmap.getOrDefault(sum[i],0)+1);
        }
        System.out.println(count);
    }
}