c - mod 在这个 DP 问题中有什么神奇的用处，底层算法是什么？

Question

DP问题如下:给定一个非负数列表和一个目标整数k，编写一个函数来检查该数组是否具有大小至少为2且总和为k的倍数的连续子数组，也就是说，求和为 n*k，其中 n 也是一个整数。

示例 1:

输入:[23, 2, 4, 6, 7], k=6输出:真解释:因为 [2, 4] 是大小为 2 且总和为 6 的连续子数组。

示例 2:

输入:[23, 2, 6, 4, 7], k=6输出:真解释:因为 [23, 2, 6, 4, 7] 是一个大小为 5 且总和为 42 的连续子数组。

我花了相当多的时间来理解这个问题的以下解决方案:

typedef struct e_s {
    int mod;
    int idx;
    struct e_s *shadow;
} e_t;
#define SZ 1024
e_t *lookup(e_t **set, int mod) {
    e_t *e = set[mod % SZ];
    while (e && e->mod != mod) {
        e = e->shadow;
    }
    return e;
}
void put(e_t **set, e_t *e, int mod, int idx) {
    e->mod = mod;
    e->idx = idx;
    e->shadow = set[mod % SZ];
    set[mod % SZ] = e;
}
bool checkSubarraySum(int* nums, int numsSize, int k) {
    int i, s, found = 0;

    e_t buff[10000];
    int n;

    e_t *set[SZ] = { 0 }, *e;

    put(set, &buff[n ++], 0, -1);

    s = 0;
    for (i = 0; i < numsSize; i ++) {
        s += nums[i];
        if (k) s = s % k;
        e = lookup(set, s);
        if (e) {
            if (i - e->idx >= 2) {
                found = 1;
                break;
            }
        } else {
            put(set, &buff[n ++], s, i);
        }
    }

    return found;
}

我什至在这里追踪了一个例子，这花了很长时间，但我想不出为什么 mod 值在这个问题中很重要，或者即使我追踪正确。

Example:
Input = 23, 2, 6, 4, 7
k = 6

buff = [e_t, e_t, ...] (size = 10000)
SZ = 1024
set = [NULL, NULL, ...] (size = 1024)

put(set, &buff[0], 0, -1);
Now n = 1

buff = [(0, -1, NULL), e_t, e_t...]
set = [(0, -1, NULL), NULL, NULL...]

i = 0
s = 0
s = 23
s = 5
e = NULL
put(set, &buff[1], 5, 0);
Now n = 2

buff = [(0, -1, NULL), (5, 0, NULL), e_t...]
set = [(0, -1, NULL), NULL, NULL, NULL, NULL, (5, 0, NULL), ...]

i = 1
s = 7
s = 1
e = NULL
put(set, &buff[2], 1, 1);
Now n = 3

buff = [(0, -1, NULL), (5, 0, NULL), (1, 1, NULL), e_t...]
set = [(0, -1, NULL), (1, 1, NULL), NULL, NULL, NULL, (5, 0, NULL), ...]

i = 2
s = 7
s = 1
e = (1, 1, NULL)

i = 3
s = 5
e = (5, 0, NULL)

Since i = 3, and e->idx = 0, (i - e->idx >= 2) evaluates to True. The function returns true. Why though...?

归根结底，我的问题归结为这里使用的是哪种算法？链表怎么了？我是否正确追踪了这一点？

Answer 1

该算法从索引 0 开始遍历数组。它维护到目前为止看到的数组元素的和模 k。这个总和是s。一旦为当前元素更新了 s，就会在哈希表中查找值 s，以便获得总和 A[ 0]+...+A[i] % k 等于 s。如果找到该索引并且到当前位置的距离大于或等于 2，则算法返回。如果没有索引，则当前索引存储在哈希表中，用于获取值 s。这个想法是如果 (A[0]+...+A[i] % k) = (A[0]+...+A[i]+...+A[j] % k) 然后 A[i+1]+...+A[j] % k = 0。

代码中有两个模数，一个是模 k 并且源自 k 的倍数等于 0 % k。第二个模数是模数 SZ，用于寻址 hash-table。 (这里称为 set)。此哈希表使用链表(使用 shadow 字段)来解决冲突。

哈希表节点的内存在 buff 数组中静态分配。

SZ 的值是作者任意选择的，以确保平均冲突率。

给定 k 的最大值，我们可以完全摆脱哈希表和节点，只使用大小为 10000 的数组来存储每个 mod 的索引.