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.

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

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

Input: nums = [1]
Output: []

• Soruda bize n elemanlı bir liste veriliyor ve bu listedeki elemanlar [1,n] arası değerler alabilir deniyor.Bu listeki bazı elemanlar 1 kere yazılmış bazıları ise 2 kere.Listede 2 kere yazılan elemanları bulmamız isteniyor.
• Çözüm için şöyle bir yol kullanabiliriz.Liste [4,3,2,7,8,2,3,1] olsun.Liste içinde ilk elemandan başlayarak dolaşmaya başlarız.Ve (elamanlar-1) index olarak düşünüp(çünkü 8 elemanlı bir listede index 0-7 arasında olabilir) o indexteki sayıyı -1 ile çarparız.
• Örneğin ikinci eleman 3 -> index(3-1=2)->2.
• indexte 2 var -> eksi mi kontrol et -> 2yi -1 ile çarp
• Liste içinde dolaşmaya devam ederken aynı eleman geldiğinde aynı indexi tekrar -1 ile çarpmaya gideriz.- Bu noktada çarpma işleminden önce sayının negatif olup olmadığını kontrol ederiz.
• Yine 3’e geldiğimizde -> index(3-1=2) -> 2. indexte -2 var -> demek ki 3 iki kez kullanılmış.
• Eleman eğer negatif değerli ise biz bu indexe daha önce gelmişizdir.Demekki şuan bulunduğumuz eleman listede birden fazla kez bulunuyor.
• Bu elemanı result listemize atarız.

    def findDuplicates(self, nums: List[int]) -> List[int]:
        result = []
        for n in nums:
            n = abs(n)
            if nums[n-1]>0:
                nums[n-1]*=-1
            else:
                result.append(n)
        return result