219. Contains Duplicate II---数组中两个重复的数字的下标最多相差k

2019-11-08 03:23:38

字体：大中小

来源：转载

供稿：网友

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. 方法一、hash

bool containsNearbyDuplicate(vector<int>& nums, int k){ int len = nums.size(); if(len<0) { return false; } map<int,int> mp; for(int i=0; i<len; i++) { if(mp.find(nums[i]) != mp.end()) { if((i-mp[nums[i]])<=k) { return true; break; } else { mp[nums[i]] = i; } } else { mp.insert(pair<int,int>(nums[i],i)); } } return false;}

方法二、集合的方法

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

上一篇：针对数据库中含大字段类型字段的表，进行数据迁移

下一篇：319. Bulb Switcher