3Sum With Multiplicity LeetCode solution in Python

1
class Solution:
2
    def threeSumMulti(self, arr: List[int], target: int) -> int:
3
        arr.sort()
4
        count = 0
5
        for i in range(0, len(arr) - 2):
6
            rem_sum = target - arr[i]
7
            hash_map = {}
8
            for j in range(i + 1, len(arr)):
9
                if arr[j] > rem_sum:
10
                    break
11
                if rem_sum - arr[j] in hash_map:
12
                    count = count + hash_map[rem_sum - arr[j]]
13
                # update the hash_map
14
                hash_map[arr[j]] = hash_map.get(arr[j], 0) + 1
15
        return count % 1000000007