Algorithm: Duplicate Elements in an Array

Title:
Given an integer array nums. Return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

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

Example 2:

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

Example 3:

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

Hints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Source: LeetCode
Link: https://leetcode-cn.com/problems/contains-duplicate

Implementation in Go.
First method, sort first, then check each element.

func containsDuplicate(nums []int) bool {
	sort.Ints(nums)
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] == nums[i+1] {
			return true
		}
	}
	return false
}

Second method, use a hash table for checking:

func containsDuplicate(nums []int) bool {
	m := make(map[int]bool)
	for i := 0; i < len(nums); i++ {
		if m[nums[i]] {
			return true
		}
		m[nums[i]] = true
	}
	return false
}

Third method, implement a simple hash table yourself, which only has keys without values:

func containsDuplicate(nums []int) bool {
	hash := InitHashTable(len(nums))

	for i := 0; i < len(nums); i++ {
		if exist := hash.Set(nums[i]); exist {
			return exist
		}
	}
	return false
}

type hashNode struct {
	key   int
	next  *hashNode
}

// HashTable structure
type HashTable struct {
	table  []*hashNode
	length int
}

func InitHashTable(n int) *HashTable {
	return &HashTable{
		table:  make([]*hashNode, n),
		length: n,
	}
}

func (hash *HashTable) GetHashCode(key int) int {
	return int(math.Abs(float64(key))) % hash.length
}

// Set method to insert an element
func (hash *HashTable) Set(key int) bool {
	index := hash.GetHashCode(key)

	// No element at this position yet
	if hash.table[index] == nil {
		hash.table[index] = &hashNode{
			key: key,
		}
	} else {
		node := hash.table[index]
		for {
			// If key is the same, override and return old value
			if node.key == key {
				return true
			}
			// Can insert the element
			if node.next == nil {
				node.next = &hashNode{
					key: key,
				}
				return false
			}
			// Next search
			node = node.next
		}
	}
	return false
}

Memory consumption can be further reduced by controlling the index size of the hash table:

func containsDuplicate(nums []int) bool {
	hash := InitHashTable(len(nums) / 2)
	... ...
}

func InitHashTable(n int) *HashTable {
	if n == 0 {
		n = 1
	}
	... ...
}