leetcode weekly contes 352

本周事情太多，没有时间参加周赛，只能赛后补充题解了。第三题是个好题目，其余的题目感觉比较水。

2760. 最长奇偶子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。

请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 <= l <= r < nums.length) 且满足以下条件的 最长子数组 ：

nums[l] % 2 == 0
对于范围 [l, r - 1] 内的所有下标 i ，nums[i] % 2 != nums[i + 1] % 2
对于范围 [l, r] 内的所有下标 i ，nums[i] <= threshold

以整数形式返回满足题目要求的最长子数组的长度。

注意：子数组 是数组中的一个连续非空元素序列。

示例 1：

输入：nums = [3,2,5,4], threshold = 5
输出：3
解释：在这个示例中，我们选择从 l = 1 开始、到 r = 3 结束的子数组 => [2,5,4] ，满足上述条件。
因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。

示例 2：

输入：nums = [1,2], threshold = 2
输出：1
解释：
在这个示例中，我们选择从 l = 1 开始、到 r = 1 结束的子数组 => [2] 。
该子数组满足上述全部条件。可以证明 1 是满足题目要求的最大长度。

示例 3：

输入：nums = [2,3,4,5], threshold = 4
输出：3
解释：
在这个示例中，我们选择从 l = 0 开始、到 r = 2 结束的子数组 => [2,3,4] 。 
该子数组满足上述全部条件。
因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= threshold <= 100

地址

https://leetcode.cn/contest/weekly-contest-352/problems/longest-even-odd-subarray-with-threshold/

题意

直接模拟

思路

可以直接进行模拟即可，时间复杂度为 $O(n^2)$，还可以继续优化到 $O(n)$ 即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        int n = nums.size();
        int res = 0;
        
        auto check = [&](int l, int r) {
            if (nums[l] % 2 != 0) {
                return false;
            }  
            for (int i = l; i < r; i++) {
                if ((nums[i] % 2) == (nums[i + 1] % 2)) {
                    return false;
                }
            }
            for (int i = l; i <= r; i++) {
                if (nums[i] > threshold) {
                    return false;
                }
            }
            return true;
        };
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (check(i, j)) {
                    res = max(res, j - i + 1);          
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    int longestAlternatingSubarray(vector<int>& nums, int threshold) {
        int n = nums.size();
        int i = 0;
        int res = 0;
        while (i < n) {
            while (i < n && ((nums[i] & 1) || nums[i] > threshold)) {
                i++;
            }
            if (i >= n) {
                break;
            }
            int start = i;
            i++;
            while (i < n && nums[i] <= threshold && (nums[i] % 2) != (nums[i - 1] % 2)) {
                i++;
            }
            res = max(res, i - start);
        }
        return res;
    }
};

2761. 和等于目标值的质数对

给你一个整数 n 。如果两个整数 x 和 y 满足下述条件，则认为二者形成一个质数对：

1 <= x <= y <= n
x + y == n
x 和 y 都是质数

请你以二维有序列表的形式返回符合题目要求的所有 [xi, yi] ，列表需要按 xi 的 非递减顺序 排序。如果不存在符合要求的质数对，则返回一个空数组。

注意：质数是大于 1 的自然数，并且只有两个因子，即它本身和 1 。

示例 1：

输入：n = 10
输出：[[3,7],[5,5]]
解释：在这个例子中，存在满足条件的两个质数对。 
这两个质数对分别是 [3,7] 和 [5,5]，按照题面描述中的方式排序后返回。

示例 2：

输入：n = 2
输出：[]
解释：可以证明不存在和为 2 的质数对，所以返回一个空数组。

提示：

1 <= n <= 106

地址

https://leetcode.cn/contest/weekly-contest-352/problems/prime-pairs-with-target-sum/

题意

数学问题

思路

素数筛选法，通过素数筛选法将所有的素数筛选出来，然后预处理即可。
依次尝试每个素数 $x$，然后检测 $n-x$ 是否也同时为素数，依次筛选出所有符合的素数对即可，为了防止重复，我们限定 $x \le n - x$ 即可。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
空间复杂度：$O(n)$，其中 $n%$ 为数组的长度。

代码

class Solution {
public:
    vector<vector<int>> findPrimePairs(int n) {
        unordered_set<int> primer;
        vector<bool> visit(n + 1, false);
        for (int i = 2; i <= n; i++) {
            if (visit[i]) continue;
            primer.emplace(i);
            for (int j = i; j <= n; j += i) {
                visit[j] = true;
            }
        }
        vector<vector<int>> res;
        for (auto v : primer) {
            if (v <= n - v && primer.count(n - v)) {
                res.push_back({v, n - v});
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};

2762. 不间断子数组

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：

i，i + 1 ，…，j 表示子数组中的下标。对于所有满足 i <= i1, i2 <= j 的下标对，都有 0 <= |nums[i1] - nums[i2]| <= 2 。

请你返回 不间断 子数组的总数目。

子数组是一个数组中一段连续非空的元素序列。

示例 1：

输入：nums = [5,4,2,4]
输出：8
解释：
大小为 1 的不间断子数组：[5], [4], [2], [4] 。
大小为 2 的不间断子数组：[5,4], [4,2], [2,4] 。
大小为 3 的不间断子数组：[4,2,4] 。
没有大小为 4 的不间断子数组。
不间断子数组的总数目为 4 + 3 + 1 = 8 。
除了这些以外，没有别的不间断子数组。

示例 2：

输入：nums = [1,2,3]
输出：6
解释：
大小为 1 的不间断子数组：[1], [2], [3] 。
大小为 2 的不间断子数组：[1,2], [2,3] 。
大小为 3 的不间断子数组：[1,2,3] 。
不间断子数组的总数目为 3 + 2 + 1 = 6 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-352/problems/continuous-subarrays/

题意

滑动窗口

思路

不错的题目，比赛的时候想到了使用滑动窗口，但是滑动窗口确实没有想好怎么写，只需要维护当前以 $i$ 为结尾时的最大窗口即可。此时区间 $[j,i]$ 内的子数组 $[i,i],[j+1,i],[j+2,i],\cdots, [i,i]$ 均满足题目要求，此时一共有 $j-i+1$ 个符合要求的子数组。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示子数组的数目。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long ans = 0;
        multiset<int> cnt;
        for (int i = 0, j = 0; i < n; i++) {
            cnt.emplace(nums[i]);
            while (*cnt.rbegin() - *cnt.begin() > 2) {
                cnt.erase(cnt.find(nums[j++]));
            }
            ans += i - j + 1;
        }
        return ans;
    }
};

2763. 所有子数组中不平衡数字之和

一个长度为 n 下标从 0 开始的整数数组 arr 的 不平衡数字 定义为，在 sarr = sorted(arr) 数组中，满足以下条件的下标数目：

0 <= i < n - 1 ，和
sarr[i+1] - sarr[i] > 1

这里，sorted(arr) 表示将数组 arr 排序后得到的数组。

给你一个下标从 0 开始的整数数组 nums ，请你返回它所有 子数组 的 不平衡数字 之和。

子数组指的是一个数组中连续一段非空的元素序列。

示例 1：

输入：nums = [2,3,1,4]
输出：3
解释：总共有 3 个子数组有非 0 不平衡数字：
- 子数组 [3, 1] ，不平衡数字为 1 。
- 子数组 [3, 1, 4] ，不平衡数字为 1 。
- 子数组 [1, 4] ，不平衡数字为 1 。
其他所有子数组的不平衡数字都是 0 ，所以所有子数组的不平衡数字之和为 3 。

示例 2：

输入：nums = [1,3,3,3,5]
输出：8
解释：总共有 7 个子数组有非 0 不平衡数字：
- 子数组 [1, 3] ，不平衡数字为 1 。
- 子数组 [1, 3, 3] ，不平衡数字为 1 。
- 子数组 [1, 3, 3, 3] ，不平衡数字为 1 。
- 子数组 [1, 3, 3, 3, 5] ，不平衡数字为 2 。
- 子数组 [3, 3, 3, 5] ，不平衡数字为 1 。
- 子数组 [3, 3, 5] ，不平衡数字为 1 。
- 子数组 [3, 5] ，不平衡数字为 1 。
其他所有子数组的不平衡数字都是 0 ，所以所有子数组的不平衡数字之和为 8 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= nums.length

地址

https://leetcode.cn/contest/weekly-contest-352/problems/sum-of-imbalance-numbers-of-all-subarrays/

题意

二分查找

思路

二分查找的思路比较简单，感觉比第三题要简单不少，主要涉及到一个变化即可，搞清楚在一个排序数组中增加一个元素后，数组的变化即可。建设现在有 $n$ 个元素的数组 $A$，此时数组中所有元素均已排序，然后我们此时需要往里面插入一个元素 $x$ ，使得数组仍然变为有序，假设 $x$ 最后插入在两个元素 $A_i,A_{i+1}$ 之间，此时一定满足 $A_i \le x \le A_{i+1}$，假设插入之前数组中含有不平衡的数字个数为 $C$ 个，此时我们需要观察以上变化，共分为三种情况：
- $$
- 假设 $x - A_i > 5, A_{i+1}-x > 5$ 时：
- 假设 $x - A_i 5, A_{i+1}-x > 5$ 时：
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示子数组的数目。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int sumImbalanceNumbers(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        for (int i = 0; i < n; i++) {
            set<int> cnt;
            int tot = 0;
            cnt.emplace(nums[i]);
            for (int j = i + 1; j < n; j++) {
                int x = nums[j];
                auto it = cnt.lower_bound(x);
                if (it == cnt.end()) {
                    int a = *cnt.rbegin();
                    if (x - a > 1) {
                        tot++;
                    }
                } else if (it == cnt.begin()) {
                    int a = *cnt.begin();
                    if (a - x > 1) {
                        tot++;
                    }
                } else {
                    int a = *it;
                    it--;
                    int b = *it;
                    if (a - b > 1) {
                        if (a - x > 1 && x - b > 1) {
                            tot++;
                        } else if (a - x <= 1 && x - b <= 1) {
                            tot--;
                        }
                    }
                }
                cnt.emplace(nums[j]);
                res += tot;
            }
        }
        return res;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← leetcode biweekly contes 107 leetcode biweekly contes 108 →

扫描二维码，分享此文章