題目連結:
題目意譯:
給定一整數陣列 nums 以及一整數 k ,找到陣列中是否存在兩個索引值 i 和 j ,滿足 nums[i] = nums[j] 且 i 與 j 差值之絕對值不超過 k 。
範例測資:
範例 1:
輸入: nums = [1,2,3,1],k = 3
輸出: true
範例 2:
輸入: nums = [1,0,1,1],k = 1
輸出: true
範例 3:
輸入: nums = [1,2,3,1,2,3],k = 2
輸出: false
解題思維:
將原陣列 nums 裡的所有值與它們的索引值綁在一起(可以自己寫資料結構,或是用內建的資料型態儲存),然後先依據值的大小由小排到大(大到小也行),再根據索引值的大小再根據大小排(同樣地,小到大或大到小皆可)。
這樣子一來,值相同的數字就會排在一起,而且按照索引值排序。所以只要掃過一次,每次跟該元素的前一個元素做比較。如果值一樣,且索引值之差 ≦ k,則即符合題目的要求,回傳真(True);反之,如果掃完之後,沒有遇到任何符合的情況發生,則回傳假(False)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。