力扣-2597.-美丽子集的数目
目录
力扣 2597. 美丽子集的数目
- 方案一（有bug，不知啥问题）
分析
题意：求一个数组(长度n)任意两个元素绝对值都不为K的子数组 (原数组子集) 个数。
解法：
用数组维护一个map mp (key为元素值，value表示该key在数组中存在的个数)；
遍历整个数组(默认key按从小到大排列)，其中包含当前元素的符合题意的子数组的个数为
t i
2 b − b ( b
n − m p [ v + k ] ) ti = 2^b - b (b = n - mp[v+k])
t
i
=
2
b
−
b
(
b
=
n
−
m
p
[
v
k
]) 。
减b是为了减去单元素子集，避免单元素子集重复计算。
a n s
t 0 + t 1 + . . . . . + t n − 1 + n ans = t0 + t1 + … .. + tn-1 + n
an
s
=
t
0
t
1
…..
t
n
−
1
n
class Solution {
public:
int A(int a) {
if (a <= 0) return 0;
return (1 << a) - 1 - a;
}
int beautifulSubsets(vector<int>& nums, int k) {
map<int, int> mp;
for (int i = 0; i < nums.size(); i++) {
mp[nums[i]]++;
}
int sum = nums.size(), ans = sum;
for (pair<int, int> p : mp) {
int t = sum;
if (mp.find(p.first + k) != mp.end()) {
t -= mp[p.first + k];
}
ans += A(t);
cout << "sum=" << sum << "," << "t=" << t << endl;
sum -= p.second;
}
return ans;
}
};- 方案二