黑神话：悟空
《黑神话：悟空》上线（8月20日）至今已经过去了半个月的时间，从刚开始的全网热议，甚至官方都出来评论，到现在已经渐渐恢复平静。
非游戏圈内人士，或者对数据不敏感的网友，或许会陷入“错觉”，觉得《黑神话：悟空》已经开始失去势头了。
但事实上，《黑神话：悟空》还在不断创造新的历史。
据机构最新统计，《黑神话：悟空》上线仅两周销量已超1800万份，营销收入达8.67亿美元。
要知道，上线前两周，网友们还在讨论《黑神话：悟空》能不能卖到300万份，能不能收支平衡；上线前一周，还在讨论能不能冲上500万份的门槛；上线前三天，还在幻想着第一波销量过后，慢慢卖，利用长尾效应冲上1000万份。
如今，不到一个月的时间，这一数字已经达到了1800万，比之前最乐观的预期高出了好几个级别。
我们之前提到过，深圳和杭州两地竞争力不大，但凭借这一波1800万的销量，加上后续的DLC和IP续集开发，保证能赚100亿，这已经不是几十个月年终奖的事了，而是整个游戏工作室集体财务自由。
是的，我指的是整个游戏工作室。
游戏科学30%以上的股份是老板持有，另外30%+的股份是员工集体持有。
有时候我们会调侃有些项目三年不开，开通三年就盈利，比如《黑神话：悟空》，开通四年才收官，开通三年就赚了几百亿，回报率25倍。
...
回到主题。
今天是星期五，这里有一道不太难的算法题。
标题描述
平台：
问题编号：992
给定一个正整数数组A，如果A的一个子数组中不同整数的个数恰好为K，则A的这个连续的、且不一定不同的子数组称为好子数组。
例如，中有 3 个不同的整数：1、2 和 3。
返回 A 中好子数组的数量。
示例 1：
输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
示例 2：
输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4]
暗示：
滑动窗口
对于每个原始数组：
找到其左边满足不同字符下标的“最远”，记为，此时形成的区间为
找到其左边满足不同字符下标的“最远”，记为，此时形成的区间为
那么对于实际上表示右边界的（必须包含），不同字符的数量“刚好”是子数组的数量
我们使用下数组来存储每个位置的 p；我们使用上数组来存储每个位置的 j。
每个位置的累计总数即为答案。
计算下部数组和上部数组的过程可以使用双指针。
Java 代码：
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
int n = nums.length, ans = 0;
int[] lower = new int[n], upper = new int[n];
find(nums, lower, k);
find(nums, upper, k - 1);
for (int i = 0; i < n; i++) ans += upper[i] - lower[i];
return ans;
}
void find(int[] nums, int[] arr, int k) {
int n = nums.length;
int[] cnt = new int[20010];
for (int i = 0, j = 0, sum = 0; j < n; j++) {
if (++cnt[nums[j]] == 1) sum++;
while (sum > k) {
if (--cnt[nums[i++]] == 0) sum--;
}
if (sum == k) arr[j] = i;
}
}
}
C++代码：
class Solution {
public:
int subarraysWithKDistinct(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
vector<int> lower(n, 0), upper(n, 0);
find(nums, lower, k);
find(nums, upper, k - 1);
for (int i = 0; i < n; i++) ans += upper[i] - lower[i];
return ans;
}
void find(vector<int>& nums, vector<int>& arr, int k) {
int n = nums.size();
unordered_map<int, int> cnt;
int i = 0, j = 0, sum = 0;
for (j = 0; j < n; j++) {
if (++cnt[nums[j]] == 1) sum++;
while (sum > k) {
if (--cnt[nums[i++]] == 0) sum--;
}
if (sum == k) arr[j] = i;
}
}
};
代码：
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
n, ans = len(nums), 0
lower, upper = [0] * n, [0] * n
self.find(nums, lower, k)
self.find(nums, upper, k - 1)
return sum(upper[i] - lower[i] for i in range(n))
def find(self, nums, arr, k):
n = len(nums)
cnt = defaultdict(int)
i, j, sumv = 0, 0, 0
while j < n:
if cnt[nums[j]] == 0:
sumv += 1
cnt[nums[j]] += 1
while sumv > k:
cnt[nums[i]] -= 1
if cnt[nums[i]] == 0:
sumv -= 1
i += 1
if sumv == k:
arr[j] = i
j += 1
终于
超划算的会员折扣渠道还在哦~
使用福利折扣通道//?=可延长年度会员有效期两个月，季度会员有效期额外延长两周，此外每月还有超大额专属实物福利发放。
我是宫水三叶，我会每天分享算法知识，和大家聊聊最近的所见所闻。