怎么制作网站应用,有哪些做策划的用的网站,互联网建筑公司,网络营销是什么时候兴起的文章目录 Tag题目来源题目解读解题思路方法一#xff1a;哈希表方法二#xff1a;滑动窗口 其他语言python3哈希表python3滑动窗口 写在最后 Tag
【哈希表】【滑动窗口】【数组】 题目来源
219. 存在重复元素 II 题目解读
判断在数组中有没有相同的元素小于一定的距离。 解… 文章目录 Tag题目来源题目解读解题思路方法一哈希表方法二滑动窗口 其他语言python3哈希表python3滑动窗口 写在最后 Tag
【哈希表】【滑动窗口】【数组】 题目来源
219. 存在重复元素 II 题目解读
判断在数组中有没有相同的元素小于一定的距离。 解题思路
方法一哈希表
我们维护一个哈希表来记录数组中的元素以及上一次出现的位置如果上一次出现的位置和这一次出现的位置之差小于等于 k那就返回 true否则返回 false。
实现代码
class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {int n nums.size();unordered_mapint, int mp;for (int i 0; i n; i) {if (mp.count(nums[i]) (i - mp[nums[i]] k)) {return true;}mp[nums[i]] i;}return false;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为数组 nums 的长度。
空间复杂度 O ( n ) O(n) O(n)使用哈希表记录数组中元素上一次出现的位置。
方法二滑动窗口
换一个思路我们只要判断在长度为 k 的窗口中是否有重复的元素出现即可。在滑窗没满之前就向滑窗中加入元素加入之前判断滑窗内是否有当前要加入的元素如果有直接返回 false当滑窗满了滑动滑窗当前的 nums[i] 要进入滑窗那么 nums[i - k - i] 要退出滑窗判断滑窗内是否有当前要加入的元素如果有直接返回 false。
如果滑窗滑到数组末尾都没有返回 true就返回 false。
实现代码
class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {unordered_setint s;int n nums.size();for (int i 0; i n; i) {if (i k) {s.erase(nums[i - k - 1]);}if (s.count(nums[i])) return true;s.emplace(nums[i]);}return false;}
};时间复杂度 O ( n ) O(n) O(n) n n n 为数组 nums 的长度。
空间复杂度 O ( k ) O(k) O(k)使用无序集合记录滑窗中的元素。 其他语言
python3哈希表
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) - bool:pos {}for i, num in enumerate(nums):if num in pos and i - pos[num] k:return Truepos[num] ireturn Falsepython3滑动窗口
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) - bool:s set()for i, num in enumerate(nums):if i k:s.remove(nums[i - k - 1])if num in s:return Trues.add(num)return False写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
