未分類

Contains Duplicate II

Array, Go, HashTable, LeetCode

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

提示 解題應用
HashTable HashMap

Default:

1
2
3
func containsNearbyDuplicate(nums []int, k int) bool {
}

解答思路:

這次要檢查是否存在一組值相同而且彼此的index值差不大於k，這邊要注意到一點是雖然是要找一組，但是也有可能出現3個或以上相同的值，而這些值只要有一組的index不大於k就算符合條件，並沒有強制規定該值一定只有兩個(一組)，所以我們在取出值的同時，除了判斷其是否存在，也不過多了再確認index值的差距，如果超過k值就將原本存在值的index給取代(因為越後面差距只會越大)，直到發現符合條件的結果。

程式碼解說:

一開始一樣先初始化一hashMap，接著再以回圈一一取出值來判斷是否存在於hashmap中，如果存在而且彼此值之間的index小於等於k就回傳true，否則就將值放入key而index做value，不存在的話就是塞入值，不然就是將原本存在值的index給取代(因為越後面差距只會越大)，最後如果找不到符合條件的結果則回傳false

1
2
3
4
5
6
7
8
9
hashTable := make(map[int]int)
for i, v := range nums {
	index, ok := hashTable[v]
	if ok && i-index <= k {
		return true
	}
	hashTable[v] = i
}
return false

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
func containsNearbyDuplicate(nums []int, k int) bool {
	hashTable := make(map[int]int)
	for i, v := range nums {
		index, ok := hashTable[v]
		if ok && i-index <= k {
			return true
		}
		hashTable[v] = i
	}
	return false
}

總結:

檢查是否存在一組值相同而且彼此的index值差不大於k，除了判斷其是否存在在hashmap，也要再確認index值的差距，如果超過k值就將原本存在值的index給取代(因為越後面差距只會越大)，直到發現符合條件的結果。

分享到