leetcode-523-连续的子数组和

连续的子数组和

题面

leetcode题目

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

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

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

example

输入：\(nums = [23,2,4,6,7]\), \(k = 6\)
输出：\(true\)
解释：\([2,4]\) 是一个大小为 \(2\) 的子数组，并且和为 \(6\) 。

数据范围

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

题解

总体思路

显然会考虑用前缀和来维护\(sum[i]\)，遍历\(i,j\)为长度\(2\)的子数组，计算\(sum[j]-sum[i]\)即可进行判断，这是\(O(n^2)\)的想法。
接着我们再来仔细考虑满足题目条件的\(sum[i]\)和\(sum[j]\)应该满足的条件。令 \[ sum[i] = a_i \times k + c_i \tag{1} \] 那么\(sum[i] - sum[j]\)的值为 \[ sum[i] - sum[j] = (a_i - a_j) \times k + (c_i - c_j) \tag{2}\] 我们已知\(sum[i] - sum[j]\) 为 \(k\) 的倍数，即为 \[ sum[i] - sum[j] = b \times k \tag{3} \] 由式子\((2)\)和\((3)\)可以得出 \[ (a_i - a_j) \times k + (c_i - c_j) = b \times k \tag{4} \] 那么由式\((4)\)我们可知 \(c_i - c_j = 0\)，即 \(c_i = c_j\)。
也就是说对于\(sum[i]\)和\(sum[j]\)我们有\(i - j >= 2\)且: \[ sum[i] \oplus k = sum[j] \oplus k \]

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;

#define _DEBUG
class Solution
{
public:
    bool checkSubarraySum(vector<int> &nums, int k)
    {
        int len = nums.size();
        int sum[len + 1];
        map<int, int> modCount;
        modCount[0] = 0;
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= len; i++)
        {
            sum[i] = sum[i - 1] + nums[i - 1];
            int mod = sum[i] % k;
#ifdef _DEBUG
            cout << "sum[i]: " << sum[i] << " mod: " << mod << " diff: " << diff << endl;
#endif
            if (modCount.count(mod) != 0)
            {
                int last = modCount[mod];
                if (i - last >= 2)
                {
                    return true;
                }
            }
            else
            {
                modCount[mod] = i;
            }
        }
        return false;
    }
};

// for test
int main()
{
    Solution s;
    vector<int> nums1{23, 2, 4, 6, 6};
    cout << s.checkSubarraySum(nums1, 7) << endl;

    vector<int> nums2{23, 2, 6, 4, 7};
    cout << s.checkSubarraySum(nums2, 13) << endl;

    return 0;
}