牛客 统计好元组

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

链接：https://ac.nowcoder.com/acm/contest/10325/A 来源：牛客网

现在给定一个数组arr，和a,b两个数字，你要做的就是找到（i，j，k）。且满足 1. 0 <= i < j < k < arr.size() 2. |arr[i] - arr[j]| <= a 3. |arr[j] - arr[k]| <= b 统计满足条件的个数并返回(最后结果可能很大，请取1000000007的余数)。

arr.size() <= 5000 其余变量均<=1e9

2. 解题

• 枚举中间点，时间复杂度 O ( n 2 ) O(n^2) O(n2)

代码语言：javascript复制

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param arr int整型vector 
     * @param a int整型 
     * @param b int整型 
     * @return int整型
     */
    int countTriplets(vector<int>& arr, int a, int b) {
        // write code here
        int n = arr.size();
        if(n < 3) return 0;
        long long ans = 0, mod = 1e9 7;
        for(int j = 1; j < n-1; j  ) 
        {
            long long ct1 = 0, ct2 = 0;
            for(int i = 0; i < j; i  )
            {
                if(abs(arr[i]-arr[j]) <= a)
                    ct1  ;
            }
            for(int k = j 1; k < n; k  )
            {
                if(abs(arr[j]-arr[k]) <= b)
                    ct2  ;
            }
            ans = (ans ct1*ct2)%mod;
        }
        return ans;
    }
};

---

size 数组 统计

0 人点赞