leetcode 219. Contains Duplicate II 使用Map记录index遍历查询

待我称王封你为后i 2022-06-08 10:15 142阅读 0赞

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.

这道题很简单，但是要注意使用HashMap结果，建议和[leetcode 217. Contains Duplicate 遍历 + HashSet][leetcode 217. Contains Duplicate _ _ HashSet] 一起学习。

代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    /*
     * 应该想到使用map 这种数据结构
     * */
    public class Solution 
    {
        
        public boolean containsNearbyDuplicate(int[] nums, int k) 
        {
            if(nums==null || nums.length<=1)
                return false;
            Map<Integer, Integer> map=new HashMap<Integer, Integer>();
            for(int i=0;i<nums.length;i++)
            {
                if(map.containsKey(nums[i]))
                {
                    int index=map.get(nums[i]);
                    if(i-index<=k)
                        return true;
                    map.put(nums[i], i);
                }else
                    map.put(nums[i], i);
            }
            return false;
        }
    
        //这是最笨的方法
        public boolean containsNearbyDuplicate1(int[] nums, int k) 
        {
            if(nums==null || nums.length<=1)
                return false;
            for(int i=0;i<nums.length;i++)
            {
                for(int j=i+1; j<nums.length && j<i+k;j++)
                    if(nums[i]==nums[j])
                        return true;
            }
            return false;
        }
    }

下面是C++的做法，就是使用map遍历一次即可完成

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) 
        {
            map<int, int> mmp;
            for (int i = 0; i < nums.size();i++)
            {
                int a = nums[i];
                if (mmp.find(a) != mmp.end())
                {
                    int j = mmp[a];
                    if (i - j <= k)
                        return true;
                    else
                        mmp[a] = i;
                }
                else
                    mmp[a] = i;
            }
            return false;
        }
    };

[leetcode 217. Contains Duplicate _ _ HashSet]: http://blog.csdn.net/jackzhang_123/article/details/78059836