题目地址(5999. 统计数组中好三元组数目)
请你返回好三元组的 总数目 .
输出:1
3 <= n <= 10^5
第二个关键单是枚举中间值 x,这样以 x 为中间值的递增三元组的个数就是 ycnt * zcnt(笛卡尔积),其中 ycnt 为 x 前面的比 x 小的,zcnt 为后面的比 x 大的.
比较容易想到的方法是使用两个平衡二叉树,代码:
return ans
实际上使用 sl1 就足够了.这是因为 zcnt 其实也等价于所有比 x 大的数的总数 - sl1 中比 x 大的数的个数,而这个信息通过 sl1 就足以求得.具体代码见下方代码区.我们可以省去一个 SortedList 的开销,因此不管是空间复杂度还是时间复杂度都可以获得常数级别的优化.
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题.