在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


LeetCode #219 存在重复元素II

题目

给定一个整数数组和一个整数 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

解题思路

题目要求:判断数组在指定范围内是否有两个相同的元素。

思路:

#217 存在重复元素 和 #219 存在重复元素II 的思路几乎是一摸一样,只不过是多了一个需要判断的条件罢了。
  1. for循环遍历每一个元素,在map中查找与该元素符合条件的元素。
  2. 如果map中没有符合条件的元素,则将该元素放入map中。
  3. 为下一个元素寻找符合条件的元素。

哈希遍历代码:

class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int length = nums.length;

for (int i = 0; i < length; i++){
// 只比 217 题多了 i - map.get(nums[i]) <= k 的判断
if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k){
return true;
}
map.put(nums[i], i);
}
return false;
}
}

评论