难度困难
题目描述
给你一个整数数组 nums 和一个整数 k。
如果一个子数组的和能够被 k 整除，或者在 将该子数组中的一个元素取反 后能使和被 k 整除，则称该子数组是 有效的 。
将一个元素取反意味着将其值 x 替换为 -x。
返回 最长有效子数组的长度 。如果不存在有效的子数组，则返回 0。
子数组 是数组中一个连续且非空的元素序列。
示例 1：
输入： nums = [4,1,2], k = 3
输出： 3
解释：
- 整个数组的和为 7，且
7 % 3 = 1，因此它不能被 k = 3 整除。 - 将
nums[2] = 2 取反，其和变为 4 + 1 − 2 = 3，能够被 k 整除。 - 因此，整个数组是一个有效子数组，其长度为 3。
示例 2：
输入： nums = [5,3,4], k = 7
输出： 2
解释：
- 整个数组的和为 12，且将其中任何一个元素取反都无法使其和被 7 整除。
- 然而，子数组
[3, 4] 的和为 7，无需任何取反操作即可被 k = 7 整除。 - 因此，最长有效子数组的长度为 2。
示例 3：
输入： nums = [2,2,5], k = 6
输出： 2
解释：
- 整个数组的和为 9，且将其中任何一个元素取反都无法使其和被 6 整除。
- 子数组
[2, 2] 的和为 4。将其中任意一个元素取反会使其变为 [-2, 2] 或 [2, -2]，这两者的和皆为 0。 - 因此，最长有效子数组的长度为 2。
提示：
1 <= nums.length <= 105-105 <= nums[i] <= 1051 <= k <= 3000
解法
方法一：前缀和
思考
\(n\) 可以到 \(10^5\)。若像上一题那样枚举被取反的位置，再对每种情形扫描前缀和，时间是 \(O(n^2)\)，无法在时限内完成。 \(k\le 3000\)，余数只有这么多种。
子数组和模 \(k\) 等于右端前缀减去左端前缀。取反一个元素 \(x\) 后，这个差减少 \(2x\)，右端余数等于左端余数加上 \(2(x\bmod k)\)。同一个左端余数只需要最早的前缀，更晚的位置得到的子数组更短。
这些最早位置按出现顺序处理。扫描右端点时，当前元素给出取反所用的余数，把已经能包含它、且还没登记过的左端余数写到目标余数上。每一对余数只写一次，右端余数上留下的最小左端点就是以该位置结尾的最长合法子数组。
设 \(p[0]=0\)， \(p[i+1]=(p[i]+\textit{nums}[i])\bmod k\)。子数组 \(\textit{nums}[L..R]\) 的和模 \(k\) 为 \(p[R+1]-p[L]\)。取反其中的 \(\textit{nums}[t]\) 时，令 \(a=\textit{nums}[t]\bmod k\)，和减少 \(2\textit{nums}[t]\)。存在 \(t\in[L,R]\) 满足
\[ p[R+1]\equiv p[L]+2a\pmod{k} \]
时，该子数组合法。完全不取反时，条件是 \(p[R+1]\equiv p[L]\)。长度是 \((R+1)-L\)，固定右端点时左端点越小越好。
\(\textit{first}[q]\) 是余数 \(q\) 第一次出现的前缀下标。把出现过的余数按 \(\textit{first}\) 从小到大排成 \(\textit{order}\)。 \(\textit{best}[s]\) 保存右端前缀余数为 \(s\) 时目前可用的最小左端点，初始为 \(\textit{first}[s]\)；余数尚未出现时写成哨兵。初始值对应完全不取反。
从左到右扫描下标 \(i\)，令 \(a=\textit{nums}[i]\bmod k\)。指针记下每个 \(a\) 已经处理到 \(\textit{order}\) 的哪里。 \(\textit{first}[q]\le i\) 的余数 \(q\) 都能把位置 \(i\) 包进子数组，于是
\[ t=(q+2a)\bmod k,\qquad \textit{best}[t]=\min(\textit{best}[t],\textit{first}[q]). \]
取反位置 \(i\) 之后，从 \(\textit{first}[q]\) 延伸到任意更右的端点、且右端余数为 \(t\) 的子数组都合法。指针只向前移动，每一对 \((a,q)\) 只处理一次。随后的右端点仍然包含 \(i\)， \(\textit{best}\) 中保留的是最小左端点。
\(s=p[i+1]\)。 \(\textit{best}[s]\) 不是哨兵时，用 \(i+1-\textit{best}[s]\) 更新答案。负数取模后余数落在 \([0,k)\)。
时间复杂度 \(O(n+k^2)\)，空间复杂度 \(O(n+k)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution:
def longestSubarray(self, nums: list[int], k: int) -> int:
n = len(nums)
p = [0] * (n + 1)
for i in range(n):
p[i + 1] = (p[i] + nums[i]) % k
first = [-1] * k
for i in range(n + 1):
if first[p[i]] == -1:
first[p[i]] = i
order = [q for q in range(k) if first[q] != -1]
order.sort(key=lambda q: first[q])
pos = [0] * k
best = [x if x != -1 else n + 1 for x in first]
ans = 0
for i, x in enumerate(nums):
a = x % k
while pos[a] < len(order) and first[order[pos[a]]] <= i:
q = order[pos[a]]
pos[a] += 1
t = (q + 2 * a) % k
best[t] = min(best[t], first[q])
s = p[i + 1]
if best[s] != n + 1:
ans = max(ans, i + 1 - best[s])
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59 | class Solution {
public int longestSubarray(int[] nums, int k) {
int n = nums.length;
int[] p = new int[n + 1];
for (int i = 0; i < n; ++i) {
p[i + 1] = (p[i] + nums[i]) % k;
if (p[i + 1] < 0) {
p[i + 1] += k;
}
}
int[] first = new int[k];
Arrays.fill(first, -1);
for (int i = 0; i <= n; ++i) {
if (first[p[i]] == -1) {
first[p[i]] = i;
}
}
Integer[] order = new Integer[k];
int m = 0;
for (int q = 0; q < k; ++q) {
if (first[q] != -1) {
order[m++] = q;
}
}
Arrays.sort(order, 0, m, (a, b) -> Integer.compare(first[a], first[b]));
int[] pos = new int[k];
int[] best = new int[k];
Arrays.fill(best, Integer.MAX_VALUE);
for (int q = 0; q < k; ++q) {
if (first[q] != -1) {
best[q] = first[q];
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int a = nums[i] % k;
if (a < 0) {
a += k;
}
while (pos[a] < m && first[order[pos[a]]] <= i) {
int q = order[pos[a]++];
int t = (q + 2 * a) % k;
best[t] = Math.min(best[t], first[q]);
}
int s = p[i + 1];
if (best[s] != Integer.MAX_VALUE) {
ans = Math.max(ans, i + 1 - best[s]);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 | class Solution {
public:
int longestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<int> p(n + 1);
for (int i = 0; i < n; ++i) {
p[i + 1] = (p[i] + nums[i]) % k;
if (p[i + 1] < 0) {
p[i + 1] += k;
}
}
vector<int> first(k, -1);
for (int i = 0; i <= n; ++i) {
if (first[p[i]] == -1) {
first[p[i]] = i;
}
}
vector<int> order;
for (int q = 0; q < k; ++q) {
if (first[q] != -1) {
order.push_back(q);
}
}
ranges::sort(order, [&](int a, int b) {
return first[a] < first[b];
});
vector<int> pos(k);
vector<int> best(k, INT_MAX);
for (int q = 0; q < k; ++q) {
best[q] = first[q] == -1 ? INT_MAX : first[q];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int a = nums[i] % k;
if (a < 0) {
a += k;
}
while (pos[a] < order.size() && first[order[pos[a]]] <= i) {
int q = order[pos[a]++];
int t = (q + 2 * a) % k;
best[t] = min(best[t], first[q]);
}
int s = p[i + 1];
if (best[s] != INT_MAX) {
ans = max(ans, i + 1 - best[s]);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 | func longestSubarray(nums []int, k int) int {
n := len(nums)
p := make([]int, n+1)
for i := 0; i < n; i++ {
p[i+1] = (p[i] + nums[i]) % k
if p[i+1] < 0 {
p[i+1] += k
}
}
first := make([]int, k)
for i := range first {
first[i] = -1
}
for i := 0; i <= n; i++ {
if first[p[i]] == -1 {
first[p[i]] = i
}
}
order := make([]int, 0, k)
for q := 0; q < k; q++ {
if first[q] != -1 {
order = append(order, q)
}
}
slices.SortFunc(order, func(a, b int) int {
return first[a] - first[b]
})
pos := make([]int, k)
best := make([]int, k)
for q := 0; q < k; q++ {
if first[q] == -1 {
best[q] = int(^uint(0) >> 1)
} else {
best[q] = first[q]
}
}
ans := 0
for i, x := range nums {
a := x % k
if a < 0 {
a += k
}
for pos[a] < len(order) && first[order[pos[a]]] <= i {
q := order[pos[a]]
pos[a]++
t := (q + 2*a) % k
best[t] = min(best[t], first[q])
}
s := p[i+1]
if best[s] != int(^uint(0)>>1) {
ans = max(ans, i+1-best[s])
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | function longestSubarray(nums: number[], k: number): number {
const n = nums.length;
const p = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
p[i + 1] = (p[i] + nums[i]) % k;
if (p[i + 1] < 0) {
p[i + 1] += k;
}
}
const first = new Array<number>(k).fill(-1);
for (let i = 0; i <= n; ++i) {
if (first[p[i]] === -1) {
first[p[i]] = i;
}
}
const order = Array.from({ length: k }, (_, q) => q).filter(q => first[q] !== -1);
order.sort((a, b) => first[a] - first[b]);
const pos = new Array<number>(k).fill(0);
const best = first.map(x => (x === -1 ? n + 1 : x));
let ans = 0;
for (let i = 0; i < n; ++i) {
let a = nums[i] % k;
if (a < 0) {
a += k;
}
while (pos[a] < order.length && first[order[pos[a]]] <= i) {
const q = order[pos[a]++];
const t = (q + 2 * a) % k;
best[t] = Math.min(best[t], first[q]);
}
const s = p[i + 1];
if (best[s] !== n + 1) {
ans = Math.max(ans, i + 1 - best[s]);
}
}
return ans;
}
|