02.同余性质

一、题目：⭐️⭐️523. 连续的子数组和

 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

 子数组大小 至少为 2 ，且
 子数组元素总和为 k 的倍数。
 如果存在，返回 true ；否则，返回 false 。

 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。

 示例 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 是一个整数。
 示例 3：

 输入：nums = [23,2,6,4,7], k = 13
 输出：false


 提示：

 1 <= nums.length <= 10^5
 0 <= nums[i] <= 10^9
 0 <= sum(nums[i]) <= 2^31 - 1
 1 <= k <= 2^31 - 1

二、「同余性质」

在看题解的时候发现了一个非常简便的解法，用到了「同余性质」

想要A-B为k的倍数，只需要a、b模k相同即可

证明

• 假设 A = xk + a, B = yk + b，A-B为k的倍数

• A - B = (xk + a) - (yk + b) = (x+y)k + (a-b) = zk

• a-b也为k的倍数，而a、b为A、B模k的值，故两者都在[0,k)区间内

• 所以：a=b

三、使用同余性质解决上面的题目

3.1 转化

连续子数组元素和转化为求两个下标从0开始连续子数组和的差值问题。

3.2 分析

• 元素依次累加，创建一个数组用来存下标和模k的值

• 得到的值模k

  • 如果map中不存在该值，根据同余性质，也就是不满足A-B为k的倍数，继续查找

  • 如果存在，则说明满足条件，可以return了

3.3 编码

func checkSubarraySum4(_ nums: [Int], _ k: Int) -> Bool {
    if nums.count < 2 {
        return false
    }
    var moMap: [Int : Int] = [:]
    moMap[0] = -1 // 这样才能正确的吧从0开始复合条件的找出来
    var sum: Int = 0
    for (index, n) in nums.enumerated() {
        sum += n
        let mo = sum % k
        print("sum\(sum) > \(mo)")
        if moMap.keys.contains(mo) {
            if let sameMoIndex = moMap[mo], index - sameMoIndex > 1 { // 长度至少为2
                return true
            }
        }
        else {
            moMap[mo] = index
        }
    }
    return false
}