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:
|
|
解答思路:
這次要檢查是否存在一組值相同而且彼此的index值差不大於k,這邊要注意到一點是雖然是要找一組,但是也有可能出現3個或以上相同的值,而這些值只要有一組的index不大於k就算符合條件,並沒有強制規定該值一定只有兩個(一組),所以我們在取出值的同時,除了判斷其是否存在,也不過多了再確認index值的差距,如果超過k值就將原本存在值的index給取代(因為越後面差距只會越大),直到發現符合條件的結果。
程式碼解說:
一開始一樣先初始化一hashMap,接著再以回圈一一取出值來判斷是否存在於hashmap中,如果存在而且彼此值之間的index小於等於k就回傳true,否則就將值放入key而index做value,不存在的話就是塞入值,不然就是將原本存在值的index給取代(因為越後面差距只會越大),最後如果找不到符合條件的結果則回傳false
|
|
完整程式碼:
|
|
總結:
檢查是否存在一組值相同而且彼此的index值差不大於k,除了判斷其是否存在在hashmap,也要再確認index值的差距,如果超過k值就將原本存在值的index給取代(因為越後面差距只會越大),直到發現符合條件的結果。