LeetCode 442 solution

problem

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space. 

Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:
Input: nums = [1,1,2]
Output: [1]

Constraints:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

python

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        hash_t = {}
        result = []
        for i in nums:
            hash_t[i] = hash_t.get(i,0) + 1
        for k,v in hash_t.items():
            if v >= 2 :
                result.append(k)
        return result

Solution

O(n)의 시간복잡도를 가지고 풀어야 한다는 것이 포인트이다. 리스트에 대해서 원소 확인과정이 한 번은 반드시 필요하다. 그런데 더 나아가서 하지는 말라는 의미로 볼 수 있다. 클래식한 hash-table 문제이다. 이전에 했던 것처럼 한 번 확인하면서 hash_t.get(i,0) + 1로 시원하게 확인해주고, key-value를 확인하면서 결과에 넣어주면 된다.

기본적으로 두 개나 하나 밖에 없다는 조건 때문에 가능한 해결 방법도 존재한다. 이분법적으로 - or + 적인 접근법이 가능하다. 2개인 경우는 +1로 해버리고, 아닌 경우는 -1로 해서 찾을 수 있다.