寒假每日一题——存在重复元素II

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

提示:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5
  • 示例
输入:nums = [1,2,3,1], k = 3
输出:true
解释:1的索引分别是0,3。 abs(3-0)=3,因此返回true

解法1

  • 思路

由于数据规模较大,因此不能使用暴力法。我们可以使用哈希表来存储 <元素,索引>,如果遇到重复元素,则判断i-map.get(num)是否小于等于k,是则返回true,否则进入下一次循环。循环结束返回false。时间复杂度为O(n)。

  • 代码
public boolean containsNearbyDuplicate(int[] nums, int k) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (map.containsKey(num) && i-map.get(num)<=k)
            return true;
        map.put(num,i);
    }
    return false;
}

解法2

  • 思路

我们还可以使用滑动窗口方法。窗口大小为 k+1, 当窗口大小大于 k+1时,删除窗口最左端的元素。如果出现重复元素,则返回 true。(因为在窗口内,因此它们之间距离一定小于等于k)。否则返回 false。

  • 代码
public boolean containsNearbyDuplicate(int[] nums, int k){
    HashSet<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        //这里想不明白的,可以想个例子带入进去
        if (i>k)
            set.remove(nums[i-k-1]);
        if (set.contains(nums[i]))
            return true;
        set.add(nums[i]);
    }
    return false;
}
上一篇:编写java项目依赖的基础镜像


下一篇:LeetCode——剑指 Offer 10- II. 青蛙跳台阶问题