题目

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

1
2
输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

1
2
输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

1
2
输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示：

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

题解

这道题我的思路还是比较简单的，要求是找数组里的两个重复数据，然后他们的下标只差的绝对值要满足条件：

我们用map转储数据，很容易可以找到第二次出现的数据；

遇到了相同的数字，判断差值是否满足要求，如果不满足要求，我们需要替换掉原有的数据，因为差值超过了要求，我们保留后面出现的数据才有可能满足要求；

如果是没出现过的数据，直接加入到map里就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        // 键值对为 数字-下标
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            // 如果出现了相同的数字，判断差值是否在范围内，在就返回，不然就更新
            if (map.containsKey(nums[i])) {
                if(Math.abs(i - map.get(nums[i])) <= k) {
                    return true;
                } else {
                    map.replace(nums[i], i);
                }
            } else {
                map.put(nums[i], i);
            }
        }
        return false;
    }
}