[LeetCode-Medium] Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:[4,3,2,7,8,2,3,1] 

Output:[2,3]

Golang

當下直覺寫出來的答案，覺得並不是非常好的解法

Memory 肯定是多了

func findDuplicates(nums []int) []int {
    r := make([]int, 0, len(nums) / 2)
    h := make(map[int]bool)
    for _, v:= range nums {
        if h[v] {
            r = append(r, v)
        } else {
            h[v] = true
        }
    }
    
    return r
}

other solution:

這個解法是把第一次找到的 nums[v] 換成負數

如果下一個找到的 nums[v] < 0 代表已經這個數是重複

就可以 append 進去 result

func findDuplicates(nums []int) []int {
    result := []int{}
    
    for _,v := range nums{
        if nums[helper(v)-1] < 0{
            result = append(result, helper(v))
        }else{
            nums[helper(v)-1] *= -1
        }
    }
    
    return result
}


func helper(value int) int{
    if value < 0{
        return value * -1
    }
    return value
}