LeetCode 219.Contains Duplicate II

本文主要是介绍LeetCode 219.Contains Duplicate II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.

二、输入输出

三、解题思路

• 使用map unordered_map set unordered_set multi_map可以做这道题
• 思路1：遍历vector 将<value,index>存储在map中，每次添加之前判断map是否已经存在，如果存在再判断两个index是否相差<=k 如果是，返回true，如果不是更新map中该key的value为最新值

    bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> dict;int n = nums.size();for (int i = 0; i < n; ++i) {if( dict.find(nums[i]) == dict.end() )dict.insert(make_pair(nums[i], i));else{int index = dict.find(nums[i])->second;if(abs(index - i) <= k)return true;elsedict[nums[i]] = i;}}return false;}

• 思路2：使用set或者map 但是里面不是保存所有的，里面只保存k个元素，一旦i>k就把开头超过的元素删除。假设当前遍历到index，并且添加到set中了，那么set中保存的就是[index - k, index - 1]一共k个元素，所以这时候该删除的元素是index - k - 1

    bool containsNearbyDuplicate(vector<int>& nums, int k) {if (k <= 0) return false;if (k > nums.size()) k = nums.size();unordered_set<int> s;for (int i = 0; i < nums.size(); ++i) {if (i > k) s.erase(nums[i - k - 1]);if (s.find(nums[i]) != s.end()) return true;s.insert(nums[i]);}return false;}

这篇关于LeetCode 219.Contains Duplicate II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---