本文涉及知识点
树状数组 一一映射
LeetCode 2179. 统计数组中好三元组数目
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, …, n - 1] 的 排列 。
好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。
请你返回好三元组的 总数目 。
示例 1：
输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出：1
解释：
总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。
这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。
示例 2：
输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
输出：4
解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。
提示：
n == nums1.length == nums2.length
3 <= n <= 105
0 <= nums1[i], nums2[i] <= n - 1
nums1 和 nums2 是 [0, 1, …, n - 1] 的排列。
树状数组
nums1和nums2符合以下四个性质：
一,nums1没有重复元素。
二,nums2没有重复元素。
三,nums1中的元素,nums2一定存在。
四,nums2中的元素nums1一定存在。
通过以下变换(变换一）4个性质不变，且结果也不变：
x1存在nums1中,x2不在nums1中。将nums1和nums2中的x1都换成x2。
先将x全部变成x+n+1，然后将nums[i]+n 全部变换成i+1，全部符合变换一，故结果不变。可以通过映射一次变换。
本题不区分顺序，即(x,y,z)和(y,x,z)相同。所以我枚举升序，即 x < y < z。
我们通过nums2[i]枚举中间的元素y，nums[0…i-1]的元素，如果小于y ，则是合法的x。nums[i+1…]中大于y的数，就是合法z，两者相乘。
nums[i+1…]中大于y的数的数量 = 大于y的数量 - nums[0…i-1]中大于y的数量。
nums[0…i-1]中大于y的数量 = i - nums[0…i-1]中小于y的数量
代码
核心代码
template<class ELE = int >
class CTreeArr
{
public:CTreeArr(int iSize) :m_vData(iSize + 1){}void Add(int index, ELE value){index++;while (index < m_vData.size()){m_vData[index] += value;index += index & (-index);}}ELE Sum(int index)//[0...index]之和{index++;ELE ret = 0;while (index){ret += m_vData[index];index -= index & (-index);}return ret;}ELE Sum() { return Sum(m_vData.size() - 2); }ELE Get(int index){return Sum(index) - Sum(index - 1);}
private:vector<ELE> m_vData;
};class Solution {
public:long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> mCode;for (int i = 0; i < nums1.size(); i++) {mCode[nums1[i]] = i + 1;}CTreeArr<int> treeArr(nums1.size() + 1);long long res = 0;for (auto& n : nums2) {n = mCode[n];}for (int i = 0; i < nums2.size(); i++) {const int y = nums2[i];const int i1 = treeArr.Sum(y);const long long ll2 = (nums2.size() - y) - (i - i1);res += i1 * ll2;treeArr.Add(y,1);}return res;}
};
单元测试
template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<int> nums1,nums2;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){nums1 = { 2, 0, 1, 3 }, nums2 = { 0, 1, 2, 3 };auto res = Solution().goodTriplets(nums1, nums2);AssertEx(1LL, res);}TEST_METHOD(TestMethod1){nums1 = { 4,0,1,3,2 }, nums2 = { 4,1,0,2,3 };auto res = Solution().goodTriplets(nums1, nums2);AssertEx(4LL, res);}};
}
扩展阅读
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
