C++/Java Two Sum O(n * m)
This looks very similar to Two Sum, and we will use Two Sum: Approach 3.\n\nWe just need to call our function "Two Product" :)\n\n> Update: see below for the op
This looks very similar to Two Sum, and we will use [Two Sum: Approach 3](https://leetcode.com/problems/two-sum/solution/).\n\nWe just need to call our function "Two Product" :)\n\n> Update: see below for the optimized version!\n\n**C++**\n```cpp\nint numTriplets(vector<int>& n1, vector<int>& n2) {\n    return accumulate(begin(n1), end(n1), 0, [&](int s, long n) { return s + twoProduct(n * n, n2); }) \n        + accumulate(begin(n2), end(n2), 0, [&](int s, long n) { return s +  twoProduct(n * n, n1); });\n}\nint twoProduct(long i, vector<int> &n) {\n    unordered_map<int, int> m;\n    int cnt = 0;\n    for (auto v : n) {\n        if (i % v == 0)\n            cnt += m[i / v];\n        ++m[v];\n    }\n    return cnt;\n} \n```\n\n**Java**\n```java\npublic int numTriplets(int[] n1, int[] n2) {\n    long res = 0;\n    for (long n : n1)\n        res += twoProduct(n * n, n2);\n    for (long n : n2)\n        res += twoProduct(n * n, n1);\n    return (int)res;\n}\nlong twoProduct(long i, int[] n) {\n    Map<Long, Long> m = new HashMap<>();\n    long cnt = 0;\n    for (long v : n) {\n        if (i % v == 0)\n            cnt += m.getOrDefault(i / v, 0l);\n        m.put(v, m.getOrDefault(v, 0l) + 1);\n    }\n    return cnt;\n}  \n```\n\n#### Optimized Version\nWe can memoise the result for a given `n`. This will speed up things quite a bit if there is a lot of duplicates. We can use a hashmap, or we can sort the array so duplicates are next to each other. The solution below is an improvement from ~800 ms to ~280 ms.\n\n**C++**\n```cpp\nint numTriplets(vector<int>& n1, vector<int>& n2) {\n    return countForArray(n1, n2) + countForArray(n2, n1);\n}\nint countForArray(vector<int>& n1, vector<int>& n2) {\n    int res = 0, last_res = 0, last_n = 0;\n    sort(begin(n1), end(n1));\n    for (auto i = 0; i < n1.size(); last_n = n1[i++])\n        if (n1[i] == last_n)\n            res += last_res;\n        else\n            res += last_res = twoProduct((long)n1[i] * n1[i], n2);\n    return res;\n}\nint twoProduct(long i, vector<int> &n) {\n    unordered_map<int, int> m;\n    int cnt = 0;\n    for (auto v : n) {\n        if (i % v == 0)\n            cnt += m[i / v];\n        ++m[v];\n    }\n    return cnt;\n} \n```
[]