“This is the 39th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

This is leetcode in the Biweekly Contest 72 of the fourth question, the difficulty is Hard, for me anyway, it is a little difficult, I did for an hour, but finally did not do it.

describe

You are given two 0-indexed arrays nums1 and nums2 of length n, both of which are permutations of [0, 1, …, n – 1].

A good triplet is a set of 3 distinct values which are present in increasing order by position both in nums1 and nums2. In other words, if we consider pos1v as the index of the value v in nums1 and pos2v as the index of the value v in nums2, then a good triplet will be a set (x, y, z) where 0 <= x, y, z <= n – 1, such that pos1x < pos1y < pos1z and pos2x < pos2y < pos2z.

Return the total number of good triplets.

Example 1:

Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3] Output: 1 Explanation: There are 4 triplets (x,y,z) such that pos1x < pos1y < pos1z. They are (2,0,1), (2, 2, 3), And (0,1,3). Out of those triplets, only the triplet (0,1,3) distribution < pos2y < pos2z. there is only 1 good triplet.Copy the code

Note:

n == nums1.length == nums2.length
3 <= n <= 10^5
0 <= nums1[i], nums2[i] <= n - 1
nums1 and nums2 are permutations of [0, 1, ..., n - 1].
Copy the code

parsing

Given two arrays of length n with index 0, nums1 and nums2 are permutations of [0, 1… n-1].

A good triple is a set of three different values that are incremented by position in nums1 and nums2. In other words, if we treat POS1v as an index of the median value v of NUMs1 and POS2v as an index of the median value v of nums2, then a good triple will be a set (x, y, z) where 0 <= x y, z <= n-1, Make pos1x < pos1y < pos1z and pos2x < pos2y < pos2z. As shown in example 2, we know that the order of (4,0,3) in nums1 is the same as the order of (4,0,3) in nums 2, so it is a valid good triple. Ask to return the total number of good triples.

This solution is explained in detail by the forum leader, which is actually transforming the problem. We want good triples, so we can find the number of combinations that can form triples with some element X as the middle element, and this problem is equivalent to finding, How many elements of nums1 and nums2 are to the left of X, and how many elements of nums1 and nums2 are to the right of X? Find pre from left to right, then invert nums1 and nums2, then find suf from left to right (suF needs to be reversed here), and finally multiply the numbers above the corresponding positions of the two lists and sum to get the answer.

Pre_a =[0,0,1,3]; nums1[I]; nums1[I]; Num1 [I]; suf_a=[1,2,1,0]; num1[I];

God’s solution is so simple, when it’s your turn to do it, but a chicken feather.

answer

from sortedcontainers import SortedList
class Solution(object):
    def goodTriplets(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        pos = [0] * len(nums1)
        for k,v in enumerate(nums2):
            pos[v] = k

        pos_in_b, pre = SortedList([pos[nums1[0]]]), [0]
        for n in nums1[1:]:
            pos_in_b.add(pos[n])
            pre.append(pos_in_b.bisect_left(pos[n]))

        nums1 = nums1[::-1]
        nums2 = nums2[::-1]
        for k,v in enumerate(nums2):
            pos[v] = k
        pos_in_b, suf = SortedList([pos[nums1[0]]]), [0]
        for n in nums1[1:]:
            pos_in_b.add(pos[n])
            suf.append(pos_in_b.bisect_left(pos[n]))
        suf = suf[::-1]

        result = 0
        for x,y in zip(pre, suf):
            result += x*y
        return result
        	      
		
Copy the code

The results

148/148 Test cases passed. Status: Accepted Runtime: 2604 MS Memory Usage: 42.2 MBCopy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation