leetcode72双周赛

竞赛链接

T1: 5996. 统计数组中相等且可以被整除的数对

---

思路

暴力

Code

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int n=nums.size(),ans=0;
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j){
                if(nums[i]==nums[j]&&(i*j)%k==0)
                    ans++;
            }
        return ans;
    }
};

复杂度分析

时间复杂度：O((N^2))
空间复杂度：O((1))

T2: 5997. 找到和为给定整数的三个连续整数

---

思路

数学：三个连续整数 i-1,i,i+1 的和为 3i，因此当且仅当给定整数为 3 的倍数时有解。

Code

class Solution {
public:
    vector<long long> sumOfThree(long long num) {
        if(num%3!=0)
            return {};
        long long b=num/3;
        return {b-1,b,b+1};
    }
};

复杂度分析

• 时间复杂度O((1))。
• 空间复杂度O((1))。

T3: 5998. 拆分成最多数目的偶整数之和

---

思路

贪心：从小到大使用所有的偶数，最后剩余部分不够大时，添加到上一个数中即可。

Code

class Solution {
public:
    vector<long long> maximumEvenSplit(long long sum) {
        if(sum%2!=0)
            return {};
        vector<long long>ans;
        int now=2;
        while(sum>=now){

            ans.emplace_back(now);
            sum-=now;
            now+=2;

        }

        if(sum>0){
            sum+=ans[ans.size()-1];
            ans.pop_back();
            if((sum/2-2)>=now){
                ans.emplace_back(sum/2-2);
                ans.emplace_back(sum/2+2);
            }
            else{
                ans.emplace_back(sum);
            }
        }

        return ans;
    }
};

复杂度分析

• 时间复杂度：O((\sqrt{N}))
• 空间复杂度：O((\sqrt{N}))

T4: 5999. 统计数组中好三元组数目

---

思路

树状数组/线段树
原题解,以后再补

Code

class Solution {
public:
    long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> pos(n);
        for (int i = 0; i < n; ++i) {
            pos[nums2[i]] = i;
        }

        long long ans = 0;
        tree.resize(n + 1);

        // 只需要在 [1, n-1) 范围内枚举 pos1_y 即可
        for (int i = 1; i < n - 1; ++i) {
            update(pos[nums1[i - 1]] + 1);
            int p = pos[nums1[i]];
            int t = query(p);
            ans += static_cast<long long>(t) * (n - i - p + t - 1);
        }

        return ans;
    }

    static int lowbit(int x) {
        return x & (-x);
    }

    void update(int x) {
        while (x < tree.size()) {
            ++tree[x];
            x += lowbit(x);
        }
    }

    int query(int x) {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }

private:
    vector<int> tree;
};

复杂度分析

• 时间复杂度：O((NlogN))
• 空间复杂度：O((N))

个人总结

---

本次双周赛，t1,t2,t3较为简单，t4坐大牢。。呜呜