Python O(n^2) function
How do we approach such a question?\n You can try the brute force, but it will TLE\n I always try to fall back to the Two Sum problem\n\t Can we build dictionar
* How do we approach such a question?\n* You can try the brute force, but it will TLE\n* I always try to fall back to the **Two Sum problem**\n\t* Can we build dictionaries in linear or n^2 time to avoid n^3 time?\n\t\t* We can count the number of `nums1[i]^2` for example\n\t\t* We can also count the number of `nums2[j] * nums2[k]` too\n\t\t* Then, we can loop in linear time over the `nums1[i]^2` values, and access the count of `j * k` in O(1)\n\t\t* \n* **Ultimately, don\'t be afraid of having multiple `O(n)` loops**, or doing anytype of `k * O(n)` or `k * O(n^2)`.\n\t* The biggest concern is **reducing the upper bound** as much as possible, e.g, achieving `O(n^2)` instead of `O(n^3)`\n\n* So, next time, think of two sum, and see if you can have multiple loops (e.g `k * O(x)`) but reduce the upper bound, (`x` in this case) as much as possible!\n\n```python\nclass Solution:\n    \n    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n        """\n        O(n^2)\n        """\n        \n        def check(nums1, nums2):\n            \n            # Initialize a dict: value->(value^2, count)\n            a = {}\n            for i in nums1:\n                if i not in a:\n                    a[i] = [i**2, 1]\n                else:\n                    a[i][-1] += 1\n                               \n            # Initialize a dict: nums2[i] * nums[j] -> count\n            b = collections.defaultdict(int)\n            for i in range(len(nums2)):\n                for j in range(i+1, len(nums2)):\n                    b[nums2[i]*nums2[j]] += 1\n                    \n            # Calculate the result\n            # result += i^2 count * j*k count for each combination\n            result = 0            \n            for (i, amount) in a.values():                \n                result += b[i]*amount\n            \n            return result\n        \n                                \n        # Call above function twice\n        return check(nums1, nums2) + check(nums2, nums1)\n```\n\n---\n\nIf you want to get a bit fancy, you can always spend time trying to optimize or clean up your code two \uD83D\uDE06\n\n```python\ndef calculate(a, b):\n    square_counts = collections.Counter(i**2 for i in a)\n    return sum(square_counts[b[j] * b[k]] for j in range(len(b)) for k in range(j+1, len(b)))\n\nreturn calculate(nums1, nums2) + calculate(nums2, nums1)\n```
['Python', 'Python3']