219. Contains Duplicate II

柔情只为你懂 2022-06-08 11:19 114阅读 0赞

[219. Contains Duplicate II][]

Given an array of integers and an integer *k*, find out whether there are two distinct indices*i* and *j* in the array such that **nums\[i\] = nums\[j\]** and the**absolute** difference between *i* and *j* is at most*k*.

问题描述：给定一个整数数组和整数k，找出该数组中是否存在两个不同的下标和j(i!=j)，是的nums\[i\]=nums\[j\]，且|i-j|<=k。

分析：最简单的思路是：循环遍历数组，对下标为i的元素，查找该元素的k个元素中是否有与nums\[i\]相等的元素，若有相等的则返回true；若不相等则继续循环，直至结束。使用两层循环：外层循环的结束条件是i<nums.length，内层循环的结束条件：当 m = (i+k < nums.length - 1) ? (i+k) (nums.length-1)。

class Solution \{  
    public boolean containsNearbyDuplicate(int\[\] nums, int k) \{  
        if(nums.length < 2)  
            return false;  
        int m;  
        for(int i = 0;i < nums.length;i++)\{  
            if(i+k < nums.length - 1)  
                m = i + k;  
            else  
                m = nums.length-1;  
            // m = (i+k <= nums.length - 1) ? (i+k) : (nums.length-1);  
            for(int j = i+1;j <= m;j++)\{  
                if(nums\[i\] == nums\[j\])  
                    return true;  
            \}            
        \}  
        return false;  
    \}  
\}

这是最开始自己的代码，但是提交代码时出现了如下问题：

![Center][]![Image 1][]

最后AC的代码：

class Solution {
        public boolean containsNearbyDuplicate(int[] nums, int k) {
             if(nums.length < 2)
    	            return false;
            if(k > 3000)
                return false;
            for(int i = 0;i < nums.length;i++){
                int m = (i+k < nums.length - 1) ? (i+k) : (nums.length-1);
                for(int j = i+1; j <= m;j++){
                    if(nums[i] == nums[j])
                        return true;
                }           
            }
            return false;
        }
    }

后来参考了另一种方法：将数组存入HashMap中，<K,V>分别对应<nums\[i\],i>，即nums\[i\]是唯一的。循环遍历数组，若nums\[i\]已存在hashMap中，则判断当前下标i与nums\[i\]在hashMap中对应的下标之差是否小于等于k，若满足则返回true;否则继续循环，直至循环结束。

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

[219. Contains Duplicate II]: https://leetcode.com/problems/contains-duplicate-ii/description/
[Center]: https://img-blog.csdn.net/20170923211006866?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd3VzdF9saA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Image 1]: