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

Code

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int n = nums.size(), cnt = 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)) 
                    cnt++;
        return cnt;
    }
};

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

Code

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

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

Code

class Solution {
public:
    vector<long long> maximumEvenSplit(long long finalSum) {
        vector<long long> v;
        if (finalSum % 2 != 0)  return v;
        
        long long t = finalSum / 2;
        long long cnt = 1, sum = 1;
        
        while (1) {
            long long now = cnt * 2;
            if ((t - cnt) * 2 <= now) {
                v.push_back(t * 2);
                break;
            }
            else {
                v.push_back(now);
                t -= cnt;
            }
            cnt++;
        }
        return v;
    }
};

5999. 统计数组中好三元组数目(树状数组)

题目描述

avatar

解题思路

可以参考这个题解

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;
        tr.resize(n + 1);
        
        for (int i = 1; i < n - 1; i++) {
            add(pos[nums1[i - 1]] + 1, 1);
            
            int p = pos[nums1[i]];
            int t = sum(p);
            ans += (long long)(t) * (n - i - p + t - 1);
        }
        return ans;
    }
    
    static int lowbit(int x) {
        return x & -x;
    }
    
    void add(int x, int v) { 
        for (int i = x; i < tr.size(); i += lowbit(i))   tr[i] += v;
    }
    
    int sum(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i))  res += tr[i];
        return res;
    }
    
private:
    vector<int> tr;
};
上一篇 下一篇