难度中等
题目描述
给你一个整数数组 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 <= 1000-105 <= nums[i] <= 1051 <= k <= 105
解法
方法一：枚举取反位置
思考
子数组和能被 \(k\) 整除，等价于两端前缀和模 \(k\) 相等。直接枚举每个子数组，再尝试取反其中的每个元素，大约是 \(O(n^3)\)。 \(n\le 1000\)，还需要再降一阶。
把元素 \(x\) 取反，所有包含它的子数组和都减少 \(2x\)，不包含它的子数组和不变。取反位置只有 \(n\) 种，再加上完全不取反，每种情形都只要找最长的、和能被 \(k\) 整除的子数组。
前缀和模 \(k\) 的每个余数只保留第一次出现的下标。右端点再次遇到同一余数时，左端点越早，子数组越长。不含被取反元素的子数组在原数组上已经统计过。
把 \(\textit{nums}[i]\) 取反后，包含下标 \(i\) 的子数组和减少 \(2\times\textit{nums}[i]\)，不含 \(i\) 的子数组和不变。对原数组，以及依次把每一个位置取反后的数组，分别求「和能被 \(k\) 整除的最长子数组」，答案是这些长度的最大值。
扫描时维护前缀和模 \(k\) 的余数，余数统一落到 \([0, k)\)。每个余数只记录第一次出现的下标，余数 \(0\) 初始对应下标 \(-1\)。扫到下标 \(i\) 时，若当前余数曾经出现在下标 \(j\)，则 \(\textit{nums}[j+1..i]\) 的和能被 \(k\) 整除，长度为 \(i-j\)。Python、Java、Go 和 TypeScript 用哈希表保存这些下标。C++ 用长度为 \(k\) 的数组，下标就是余数，扫描时用参数标出被取反的位置。
时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n)\)。C++ 每次重置这个数组，时间复杂度 \(O(n(n+k))\)，空间复杂度 \(O(k)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def longestSubarray(self, nums: list[int], k: int) -> int:
def f(nums: list[int], k: int) -> int:
d = {0: -1}
s = res = 0
for i, x in enumerate(nums):
s = (s + x) % k
if s in d:
res = max(res, i - d[s])
else:
d[s] = i
return res
ans = f(nums, k)
for i, x in enumerate(nums):
nums[i] = -x
ans = max(ans, f(nums, k))
nums[i] = x
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 | class Solution {
public int longestSubarray(int[] nums, int k) {
int ans = f(nums, k);
for (int i = 0; i < nums.length; ++i) {
nums[i] = -nums[i];
ans = Math.max(ans, f(nums, k));
nums[i] = -nums[i];
}
return ans;
}
private int f(int[] nums, int k) {
Map<Integer, Integer> d = new HashMap<>();
d.put(0, -1);
int s = 0, res = 0;
for (int i = 0; i < nums.length; ++i) {
s = ((s + nums[i]) % k + k) % k;
if (d.containsKey(s)) {
res = Math.max(res, i - d.get(s));
} else {
d.put(s, i);
}
}
return res;
}
}
|
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 {
public:
int longestSubarray(vector<int>& nums, int k) {
int n = nums.size();
vector<int> d(k, -2);
auto f = [&](int skip) {
fill(d.begin(), d.end(), -2);
d[0] = -1;
int s = 0, res = 0;
for (int i = 0; i < n; ++i) {
int x = i == skip ? -nums[i] : nums[i];
s = (s + x) % k;
if (s < 0) {
s += k;
}
if (d[s] != -2) {
res = max(res, i - d[s]);
} else {
d[s] = i;
}
}
return res;
};
int ans = f(-1);
for (int i = 0; i < n; ++i) {
ans = max(ans, f(i));
}
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 | func longestSubarray(nums []int, k int) int {
f := func(nums []int) int {
d := map[int]int{0: -1}
s, res := 0, 0
for i, x := range nums {
s = (s + x) % k
if s < 0 {
s += k
}
if j, ok := d[s]; ok {
res = max(res, i-j)
} else {
d[s] = i
}
}
return res
}
ans := f(nums)
for i, x := range nums {
nums[i] = -x
ans = max(ans, f(nums))
nums[i] = x
}
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 | function longestSubarray(nums: number[], k: number): number {
const f = (nums: number[]): number => {
const d = new Map<number, number>([[0, -1]]);
let s = 0,
res = 0;
for (let i = 0; i < nums.length; ++i) {
s = (s + nums[i]) % k;
if (s < 0) {
s += k;
}
if (d.has(s)) {
res = Math.max(res, i - d.get(s)!);
} else {
d.set(s, i);
}
}
return res;
};
let ans = f(nums);
for (let i = 0; i < nums.length; ++i) {
nums[i] = -nums[i];
ans = Math.max(ans, f(nums));
nums[i] = -nums[i];
}
return ans;
}
|