Leetcode219

Leetcode219：存在重复元素 II

题目描述

Leetcode219: 存在重复元素 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

解法一：基于map的判断

/*****************************************
基于map的判断
用map存放值到索引的哈希表，
然后一一查找map中是否有相同的值，
若有则判断索引差是否小于等于k，
不是则修改map中的索引值。
******************************************/
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if (nums.size()<2) return false;
        map<int, int> a;
        for (int i = 0; i<nums.size(); i++)
        {
            if (a.count(nums[i]))
            {
                if (i - a[nums[i]] <= k)
                    return true;
                else a[nums[i]] = i;
            }
            else a.insert(map<int, int>::value_type(nums[i], i));
        }
        return false;
    }
};