https://leetcode.com/problems/count-good-triplets-in-an-array/
数组的思路，数组操作的考察

题目解答

  1. from sortedcontainers import SortedList
  3. class Solution:
  4.     def goodTriplets(self, a: List[int], b: List[int]) -> int:
  5.         n = len(a)
  6.         # index table of b
  7.         bi = [x[0] for x in sorted(enumerate(b), key=lambda x:x[1])]
  8.         c = [bi[x] for x in a] # in c, element is in order for a
  11.         # left smaller
  12.         left_smaller = [0] * n
  13.         sl = SortedList()
  14.         for i in range(n):
  15.             idx = sl.bisect(c[i])
  16.             left_smaller[i] = idx
  17.             sl.add(c[i])
  19.         # right larger
  20.         right_larger = [0] * n
  21.         sl = SortedList()
  22.         for i in range(n - 1, -1, -1):
  23.             idx = sl.bisect(c[i])
  24.             right_larger[i] = len(sl) - idx
  25.             sl.add(c[i])
  27.         return sum(x * y for (x, y) in zip(left_smaller, right_larger))

题目分析

这道题很容易把人搞混，容易想不明白，但题目还是好题的。
关键的两点：

  • 利用下标、顺序等特性转化问题到一个数组上
  • 找左右两侧符合条件的元素

第一点，要保证两个数组中元素都满足顺序，可以先定下一个，然后看另一个是否满足。
如代码中所示，在c中，a里的顺序都是满足的，那么就只要看b的index是否满足升序这一属性
所以问题转化成c数组某一元素左侧小的，右侧大的元素数量

第二点，找某一侧小的元素数量，是个很经典的问题了，一般用二叉树，线段树等解决。
好在python可以直接引用sortedcontainers包，SortedList可以完成这个功能。
这个在做题中还是很好使的。