1.題目

給你一個整數數組?nums 和一個整數?k ，判斷數組中是否存在兩個 不同的索引?i?和?j ，滿足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否則，返回 false 。

2.示例

示例?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

提示

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

---

3.思路

哈希表:

????????首先看到數組中需要用到索引與對應的值，很明顯就能聯想到哈希表數據結構與相關查找以減少查找速度，通過遍歷數組將未存在于表中的數據與相應的索引存入哈希表中，然后如果遇到存在的鍵值的數據則找到數據的索引與當前遍歷的值進行絕對值相減獲取結果進行判定如果符合則返回true。如果遍歷結束都沒有滿足則返回false

4.代碼

LeetCode代碼

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {int temp;HashMap<Integer,Integer> map = new HashMap<>();for (int i=0;i< nums.length;i++){if (map.containsKey(nums[i])){temp = map.get(nums[i]);if (Math.abs(temp-i)<=k){return true;}}map.put(nums[i],i);}return false;}
}

時間復雜度為O(n),O(1)

案例詳細代碼：
?

package LeetCode18;import java.util.HashMap;public class javaDemo {public static void main(String[] args) {int nums[]= new int[]{1,2,3,1};int k = 3;
//        中間量int temp;boolean flag = false;
//        創建哈希表HashMap<Integer,Integer> map = new HashMap<>();
//        循環遍歷for (int i=0;i< nums.length;i++){
//            查找是否已經存在一樣的值if (map.containsKey(nums[i])){temp = map.get(nums[i]);
//                判斷兩者絕對值差值是否小于等于kif (Math.abs(temp-i)<=k){flag = true;break;}}
//            如果不存在鍵則把鍵值都存放到哈希表map.put(nums[i],i);}
//        輸出結果System.out.println(flag);}
}

---

會了？試試挑戰下一題！?（＾?＾●）ﾉｼ （●′?｀）?

LeetCode150道面試經典題-- 快樂數(簡單)_Alphamilk的博客-CSDN博客