Finding Pairs With a Certain Sum (Array, Hash Table, Design)

링크 - https://leetcode.com/problems/finding-pairs-with-a-certain-sum/editorial/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

Counter를 사용한 hash table를 사용해서 풀 수 있다. 먼저 nums1과 nums2의 counter를 만든 뒤, nums2는 list그대로 저장해 놓고, 값이 변경될때마다 list와 hash table를 둘 다 업데이트하면 된다.

Code

class FindSumPairs:

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.hash1 = defaultdict(int)
        self.hash2 = defaultdict(int)
        for i, num in enumerate(nums1):
            self.hash1[num] += 1
        for i, num in enumerate(nums2):
            self.hash2[num] += 1
        self.nums2 = nums2
        

    def add(self, index: int, val: int) -> None:
        self.hash2[self.nums2[index]] -= 1
        self.nums2[index] += val
        self.hash2[self.nums2[index]] += 1
        

    def count(self, tot: int) -> int:
        ans = 0
        for k, v1 in self.hash1.items():
            if tot - k in self.hash2:
                v2 = self.hash2[tot - k]
                ans += v1 * v2

        return ans
        


# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)

Complexity

여기서 n과m은 각각 nums1과 nums2의 길이이다. q1과 q2는 각각 add와 getPairs가 call된 횟수이다.

Time Complexity: O(n+m+q1+q2*n)

Space Complexity: O(n+m)