Readme

1577.Number-of-Ways-Where-Square-of-Number-Is-Equal-to-Product-of-Two-Numbers

解法1：Hash

这个方法更容易实现。我们查看数组A中的每个元素a。然后遍历数组B中的元素i，同时维护一个hash表来统计B[i]之前的B数组元素的频率。

如果a*a/B[i]存在hash表中存在并且有k个，这就意味着有k组triplet满足条件{a, B[i], a*a/B[i]}，加入ret的统计中。注意每查看完B[i]，要把B[i]也加入hash表中。

解法1：Two Pointer

如果这两个数组都排过序，那么有不需要额外空间的双指针方法。看似和two sum基本一致，但是实现起来更为麻烦。

我们知道，如果a*a < B[i]*B[j]，那么下一步是i++；如果a*a > B[i]*B[j]，那么下一步是j--；但如果a*a==B[i]*B[j]，下一步该指针移动？不应该是i++, j--。正解是：

1. 如果B[i]==B[j]，那么[i:j]区间内的k个相同的数，任意取两个都可以放入triplet，所以ret+=k*(k-1)/2，然后就可以退出了。
2. 否则的话，我们需要检查有x个与B[i]相同的数，y个与B[j]相同的数，所以ret+=x*y。然后需要把i指针右移到下一个不同的数（移动x个位置），j指针左移到下一个不同的数（移动y个位置）。