※ 引述《JIWP (神楽めあ的钱包)》之铭言：
: 2179. Count Good Triplets in an Array
: 题目的意思就是要找这样的排列[a,b,c]有几种
: 其中a,b,c,的先后顺序在nums1、nums2都一样
: 思路:
nums1 和 nums2 都是 (0~n-1) 的 premutation
先思考怎么找到 good pair 好了
可以想像要先做一个 idx 转换
nums1[i] 的这个数字在 nums2 的 index 是多少
然后就可以从左开始 iterate nums1 把他们在 nums2 的 index 做成 sortedlist
直接二分搜这个 sortedlist 就可以知道有多少数字在 nums2 也同样靠前
以 nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3] 为例好了
iterate nums1:
4 -> idx in s2 = 0, sorted index = [0]
0 -> idx in s2 = 2, sorted index = [0,2]
1 -> idx in s2 = 1, sorted index = [0,1,2]
3 -> idx in s2 = 4, sorted index = [0,1,2,4]
2 -> idx in s2 = 3, sorted index = [0,1,2,3,4]
挑 (1,4) 这个合法 pair 来观察好了
在 iterate 到 1 的时候 还没插入的 sorted index 是 [0,2]
他们代表 4,0 在 s2 中的 index 是多少
而 1 在 s2 的 index 是 1, 二分搜就可以知道有多少 index 在 s2 中也同样比较小
要怎么扩展到 triplet
就可以想像假如 iterate 到 s1[3]=516, s1[3] 在 s2 的 index 是 4
那 s1 s2 应该会长这样
s1 = [x, x, x, 516, ......]
s2 = [y, y, y, y, 516, ......]
我们刚刚知道可以用 sortedlist 知道 x 中有几个也在 y 里面, 如果是 2 个好了
s1 = [0, 1, x, 516, ......]
s2 = [y, y, 0, 1, 516, ......]
合法的 triplet 就可以用 {(0,1), 516, 剩下的数字-x-y} 算出来
同时 xy 没有相同元素
写成 prev * 1 * pos 的话
prev = len([0,1]) 代表的就是刚刚 sorted index 二分搜出来的值
pos = len(剩下的数字-x-y)
直接看 s2 会比较清楚 因为 s2 长相差不多是 [y, y, 0, 1, 516, ......, x, ......]
所以就是用 len(n) - (516 在 s2 的 index + 1) - (x 的个数)
x 的个数就是 iterate s1 的 index - prev
不想写了 我自己快看不懂了
Python code:
class Solution:
def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
idx2 = [0]*n
res = 0
for i in range(n):
idx2[nums2[i]] = i
prevIdx = SortedList([])
for i in range(n):
idx1in2 = idx2[nums1[i]]
prev = prevIdx.bisect_left(idx1in2)
prevIdx.add(idx1in2)
pos = n - (idx1in2 + 1) - (i - prev)
res += prev*pos
return res
喔对了 因为 python sortedlist 插入是 O(logn) 才能这样
不然只能乖乖用线段树或BIT 哈哈

唉 恨屁眼

干 我他妈哭了 我今天这题写超久没写出来直接抄线段书我好痛苦我好崇拜你

如果是周赛我也直接复制模板ㄚ 对ㄚ

我原本也是用二分搜寻，不过插入会爆掉，恨恨恨

这就是SortedList的不合理之处

害我跑去刻那该死的线段树