letcode 523. 连续的子数组和【前缀和and同余】

以下是lecode的一道题，可以用前缀和+同余的思想进行解题

1. 什么是前缀和

前缀和顾名思义就是一个求和运算，前多少项的和，我们用Sn表示就是 Sn = a₀+a₁+ …+a_n，现在有一个数列 11，2，8，6，9，7 那么它的前缀和数列就是，S₁=11， S₂=11+2=S₁+2=13， S₃=11+2+8=S₂+8=21， S₄=11+2+8+6=S₃+6=27， S₅=11+2+8+6+9=S₄+9=36， S₆=11+2+8+6+9+7=S₅+7=43 。

1.1 前缀和应用

求区间和，最常被用作求某一个区间的和：S_j - S_i

2. 什么是同余

若两个整数除以同一个整数得到的余数相同，就称这两个整数同余，X mod K = Y mod K；X，Y同余。

3.解题

“连续的子数组和”这道题就是 对区间和进行取模，余数为0则返回true；可以用前缀和表示就是：（ S_j - S_i）% k =0 ，由此公式我们可以推导出同余表达式 S_j % k = S_i % k；于是这道题就转换为了前缀和取模，若能找到这两个前缀和同余则返回true（ps：题目还有其他细节条件，例如子数组大小最小为2，即区间大小最小为2【j - i > 1】；前缀和取模为0 就是直接条件称成立也是返回true）

var checkSubarraySum = function(nums, k) {
    let sum = 0;
    let resArr = [];
    for(let j=0; j<nums.length;j++){
    	//前缀和
        sum += nums[j];
        let R = sum % k;
        //查找前缀和的余数在数组中出现的下标位置既i的位置
        let i= resArr.indexOf(R);
        if( (i>=0 && (j-i)>1) || (R==0 && j>=1)){
            return true;
        }
        //将余数存起来
        resArr[j] = R;
    }
    return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17