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) } -- ※ 發信站: 批踢踢實業坊(ptt-site.org.tw), 來自: 203.121.235.241 (臺灣) ※ 文章網址: https://ptt-site.org.tw/Marginalman/M.1744714766.A.B64

推 oin1104: 剩我不會線段樹了 04/15 19:06