523. 连续的子数组和

拼搏现实的明天。 2022-10-18 11:23 132阅读 0赞

> 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
> 
> **子数组大小 至少为 2 ，且  
> 子数组元素总和为 k 的倍数。**  
> 如果存在，返回 true ；否则，返回 false 。
> 
>   
> 示例 1：
> 
> 输入：nums = \[23,2,4,6,7\], k = 6  
> 输出：true  
> 解释：\[2,4\] 是一个大小为 2 的子数组，并且和为 6 。  
> 示例 2：
> 
> 输入：nums = \[23,2,6,4,7\], k = 6  
> 输出：true  
> 解释：\[23, 2, 6, 4, 7\] 是大小为 5 的子数组，并且和为 42 。   
> 42 是 6 的倍数，因为 42 = 7 \* 6 且 7 是一个整数。
> 
>

> **如果两个整数m、n满足n-m能被k整除，那么n和m对k同余**
> 
> 即 ( pre(j) - pre (i) ) % k == 0 则 pre(j) % k == pre(i) % k
> 
>

class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
             /**
             利用同余定理   
              (a-b)%k==0   可以推出 a%k==b%k
              做前缀和,如果  当前前缀和 - 历史前缀和 %k==0也就是 连续子数组和是k的倍数,那么 当前前缀和%k和历史前缀和%k相等
              */
              int sum[]=new int[nums.length+1];
              sum[0]=0;
              
             for(int i=1;i<=nums.length;i++){
                 sum[i]=sum[i-1]+nums[i-1];  //做一个前缀和
             }
    
             // 前缀和  记录截止的坐标
             HashMap<Integer,Integer> map=new HashMap();
             for(int i=0;i<sum.length;i++){
                 if(map.containsKey(sum[i]%k)){  //看下历史前缀和%k是否=当前前缀和%k
                    if(i-map.get(sum[i]%k)>=2){
                        return true;
                    }
                 }else if(!map.containsKey(sum[i]%k)){
                     map.put(sum[i]%k,i);//放进去 当前前缀和%k ,下标
                 }
             }
             return false;
        }
    }