题目描述：
给你一个 非负 整数数组 nums 和一个整数 k 。
如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 -1 。
数据范围：
$1\le n \le 2\times 10^5, 1\le nums[i] \le 10^9, 0 \le k \le 10^9$
题解：
滑动窗口：
由于存在单调性，or 运算只能越来越大。因此可以使用滑动窗口来做。
需要使用一个长度为 $32$ 的数组，维护当前窗口每一位上 $1$ 的个数。每次加入 $nums[r]$ ，更新当前窗口里面 $1$ 的个数，移除左端点 $nums[l]$ 时也要更新。
子数组 OR/AND/GCD 通用模板：
由于是 or 运算，只能越来越大，而且最多只会出现 $\log(nums[i])$ 种不同的值。因此可以直接维护当前以 $i$ 为终点的子数组中，or 值的种类。使用一个vector<pair<int, int>> orsum 表示。其中元素对 (key,val) 表示当前 orsum 为 key 时，最大的 left 为 val。这样的话 i - val + 1 就可以得到子数组 orsum >= k 时的长度了。假设已经得到了 $nums[i - 1]$ 的 orsum 数组，那么加入 $nums[i]$ 时，需要考虑将 $nums[i]$ 与里面的所有元素 or 一遍，同时需要注意去重。单调性是递减的，因为越往后，或的越少，数值只能更小。
例如 a1, a2, a3
(a1, 0)
(a1 | a2, 0), (a2, 1)
(a1 | a2 | a3, 0), (a2 | a3, 1), (a3, 2)。
key 是递减的，val 是递增的。
其实也可以先运算一遍之后，直接调用去重的 unique 函数。
为了便利计算，可以先放入 (0, i)，为了最后 or 的时候得到 (ai, i)。
原地去重：
考虑一个递减数组，原地去重操作。
假设当前数组末尾是 nums[k]，每次将需要加入的 nums[i] 与 nums[k] 对比，如果不相同，则放到 nums[k + 1] 处；相同的话则继续往后遍历。
1
2
3
4
5
6
7
| int k = 0;
for(int i = 0; i < nums.size(); ++i) {
if(nums[i] != nums[k]) {
nums[++k] = nums[i];
}
}
nums.resize(k + 1);
|
模板：
1
2
3
4
5
6
7
8
| for(int i = 0; i < n; ++i) {
for(int j = i - 1; j >= 0; --j) {
if(nums[j] ? nums[i] == nums[j]) {
break;
}
}
}
|
其中会得到这样的序列
a1?a2?a3?a4, a2?a3?a4, a3?a4, a4。
由于 lcm, gcd, |, & 具有单调性。当 nums[j] | nums[i] = nums[j] 时，表明，nums[i] 是 nums[j] 的子集，又因为 nums[j] 是左侧所有元素的子集，因此 nums[i] 是 nums[k], 0<k<=j 的子集，因此继续往前都不会有什么变化了。
同理gcd, lcm, & 也可以得到类似的结论。
而且由于单调性，所得到的序列可以进行二分。
代码：
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int getOrSum(vector<int> &nums)
{
int sum = 0;
for (int i = 0; i < 32; ++i)
{
if (nums[i] > 0)
{
sum += (1 << i);
}
}
return sum;
}
void diffVector(vector<int> &a, vector<int> &b)
{
for (int i = 0; i < 32; ++i)
{
a[i] -= b[i];
}
}
void addVector(vector<int> &a, vector<int> &b)
{
for (int i = 0; i < 32; ++i)
{
a[i] += b[i];
}
}
int minimumSubarrayLength(vector<int> &nums, int k)
{
int n = nums.size();
vector<vector<int>> cur(n, vector<int>(32));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < 32; ++j)
{
if ((nums[i] >> j) & 1)
{
cur[i][j]++;
}
}
}
int orsum = 0;
vector<int> tmp(32);
int l = 0;
int ans = INF;
for (int r = 0; r < n; ++r)
{
addVector(tmp, cur[r]);
orsum = getOrSum(tmp);
while (orsum >= k && l <= r)
{
if (orsum >= k)
{
ans = min(ans, r - l + 1);
}
diffVector(tmp, cur[l]);
orsum = getOrSum(tmp);
++l;
}
}
return ans == INF ? -1 : 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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int minimumSubarrayLength(vector<int> &nums, int k)
{
int n = nums.size();
int ans = INF;
vector<pair<int, int>> orsum;
for (int i = 0; i < n; ++i)
{
int size = 0;
orsum.emplace_back(0, i);
for (int j = 0; j < orsum.size(); ++j)
{
auto &[key, val] = orsum[j];
key |= nums[i];
if (key >= k) ans = min(ans, i - val + 1);
if (orsum[size].first == key) orsum[size].second = val;
else orsum[++size] = orsum[j];
}
orsum.resize(size + 1);
}
return ans == INF ? -1 : ans;
}
};
|