Leetcode 442. Find All Duplicates in an Array

문제

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.

주어진 길이 n의 정수 배열에 1~n의 숫자들이 있다.
이 숫자들이 1번 혹은 2번씩 등장할때, 2번 등장하는 숫자들의 배열을 리턴하시오.
단 O(n)의 시간복잡도와 O(1)의 공간복잡도를 가져야 한다.

예시

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Explanation: 나머지는 1번씩 나오는데, 2와 3만 두번 등장한다.

제한

• $n == nums.length$
• $1 <= n <= 10^5$
• $1 <= nums[i] <= n$
• nums 안의 원소는 반드시 1회 혹은 2회 등장한다.

풀이법

• 일단 1~n으로 숫자의 범위가 정해져 있기에 이 값에 -1을 하면 n개의 배열의 모든 index에 맞아 떨어진다.
• 이를 이용해 2번 등장하는것을 체크한다!

1. 주어진 nums를 순차탐색하되 아래를 확인한다, 이때 자기자신이 음수이면 양수로 바꾸어 아래로 간다.
   • 값 n에 대해 nums[n-1] 이 양수이면 음수로 변환한다.
   • 만약 nums[n-1] 이 음수일 경우, 이전의 값중 반드시 n이 한번 등장했다는 의미이기에 정답 배열에 추가한다!

• 1~2회만 등장하기에 음수인 값을 다시 되돌릴 필요는 없다.
  

코드

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans = []
        
        for i, v in enumerate(nums):
            value = v if v > 0 else -v
            # 값이 양수이면 음수로 flip
            if nums[value-1] > 0:
                nums[value-1] *= -1
            # 이미 음수이면 정답 배열에 추가.
            else:
                ans.append(value)
        
        return ans