2179. Count Good Triplets in an Array
题目的意思就是要找这样的排列[a,b,c]有几种
其中a,b,c,的先后顺序在nums1、nums2都一样
思路:
用暴力解一定挂
建立一个array来记录0~n-1在nums2对应的index
接着我们按照nums1的顺序去做一个for循环
就去找在i之前，有几个元素在nums2里的index比nums1[i]的index还小，假设有x个
并且找在i之后，有几个元素在nums2里的index比nums1[i]的index还大，假设有y个
这样能得到的组合为x*y，就这样一直做完就可以得到答案了
至于要如何找到x
就用segment tree
我们就可以快速找出到目前为止
有几个元素在nums2里的index比nums1[i]还小
接着就把nums1[i]在nums2里的index丢去segment tree做更新
当得到了x，y也就不难找了
golang code
type segementTree struct {
tree []int
}
func (this segementTree) modify(l, r, idx, val int) {
if r == l {
this.tree[idx]++
return
}
m := l + (r-l)/2
this.tree[idx]++
if val > m {
this.modify(m+1, r, 2*idx+2, val)
} else {
this.modify(l, m, 2*idx+1, val)
}
}
func (this segementTree) query(R, L, r, l, idx int) int {
if r < 0 {
return 0
}
if l == L && r == R {
return this.tree[idx]
}
M := L + (R-L)/2
if M >= r {
return this.query(M, L, r, l, 2*idx+1)
} else if l > M {
return this.query(R, M+1, r, l, 2*idx+2)
} else {
return this.query(R, M+1, r, M+1, 2*idx+2) + this.query(M, L, M, l, idx*2+1)
}
}
func goodTriplets(nums1 []int, nums2 []int) int64 {
n, ans := len(nums1), 0
nums2Idx, rec := make([]int, n), segementTree{make([]int, 4*n)}
for i := 0; i < n; i++ {
nums2Idx[nums2[i]] = i
}
rec.modify(0, n-1, 0, nums2Idx[nums1[0]])
for i := 1; i < n-1; i++ {
idx := nums2Idx[nums1[i]]
j := rec.query(n-1, 0, idx-1, 0, 0)
rec.modify(0, n-1, 0, idx)
if j == 0 {
continue
}
ans += j * (n - idx - 1 - (i - j))
}
return int64(ans)
}

剩我不会线段树了