题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是找出一个数组中的某一种三元组的数量，该三元组要求中间的值为两边值的一半。

思路分享

  • 尝试了一下普通的枚举思路，即遍历右侧，看有无相同值以及一半值。但是这样的算法，无法处理[0, 0, 0]的情况，因为 0 的一半还是 0。

  • 因此重点的学习部分在于，用怎样的思路来对数组进行预处理。

    https://leetcode.cn/problems/count-special-triplets/solutions/3700554/mei-ju-zhong-jian-qian-hou-zhui-fen-jie-5uad8/

  • 回顾上一次学习枚举中间基本思路(【Leetcode Daily】2909元素和最小的山形三元组)，是对每一位都记录了最小的那个值。

  • 但是可以稍微魔改一下，用哈希表记录数组中每个值的频次，并且去除掉已遍历的值，那不就是右侧的情况嘛。同时遍历过程中顺便用另一个哈希表记录左侧情况，如此一来，就完成了枚举中间的思路。

  • 以及，由于 Python 没有数值溢出这种东西，所以取余操作可以放最后进行，这一点真是方便不少。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def specialTriplets(self, nums: List[int]) -> int:
        suf = Counter(nums)
        pre = defaultdict(int)
        res = 0
        MOD = 1_000_000_007
        for i in nums:
            suf[i] -= 1 
            res += suf[i*2] * pre[i*2]
            pre[i] += 1

        return res % MOD