统计三元组

[编程题]统计三元组

热度指数：338 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在给定一个数组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的余数)。

示例1

输入

[7,1,8,9,0],3,3

输出

说明

只有（7，8，9）符合要求

备注:

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

算法知识视频讲解

发个offer就摆烂

1. 用参数 i 遍历数组

2. 判断 j<i 左边数组 arr[j] : abs(arr[j] - arr[i]) <= a , l += 1

3. 判断 j>i 右边数组 arr[j] : abs(arr[j] - arr[i]) <= b , r += 1

4. 对于第i轮，总共有l*r个组合结果

5. 统计总共所有的遍历结果 ans

class Solution:
    def countTriplets(self , arr , a , b ):
        # write code here
        ans = 0
        n = len(arr)
        mod = 10 ** 9 +7
        
        for i in range(n):
            
            l,r = 0,0
            for j in range(i):
                if abs(arr[j] - arr[i]) <= a:
                    l += 1
            
            for j in range(i+1, n):
                if abs(arr[j] - arr[i]) <= b:
                    r += 1
            ans = (ans + l*r ) % mod
        return ans

发表于 2021-07-18 14:19:38 回复(0)