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，就会在散列 table 中查找值 s，以便获得和 A[0]+...+A[i] % k 相等的索引至 s。如果找到这个索引并且到当前位置的距离大于等于2，则算法returns。如果没有索引，则当前索引存储在哈希值 s 的散列 table 中。这个想法是如果 (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）。这个 hash-table 使用链表（使用 shadow 字段）来解决冲突。

散列-table 节点的内存静态分配在 buff 数组中。

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

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

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

How is mod mysteriously useful in this DP problem, and what is the underlying algorithm?

c

algorithm

trace

dynamic-programming