本文讲述了python基础编程100例：第85期-基础技巧：滑动窗口 存在重复元素 II！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第85期-基础技巧：滑动窗口 存在重复元素 II

1 问题描述

给定一个整数数组和一个整数 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

初始代码

from typing import List

class Solution:

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

        #在此之间填写代码

print(Solution().containsNearbyDuplicate([1,2,3,1],3))

print(Solution().containsNearbyDuplicate([1,0,1,1],1))

print(Solution().containsNearbyDuplicate([1,2,3,1,2,3],2))

2 解题思路

标签：滑动窗口

采用滑动窗口，窗口长度最长为k，若长度不超过k只移动right边界即可

若长度超过k，则需要同时移动left。要遍历窗口内的每一个元素来判断是否和right相等。

3 解题方法

from typing import List

class Solution:

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

        a=[]

        i,j,b=0,0,len(nums)

        while i<b:

            if nums[i] in a:return True

            a.append(nums[i])

            i+=1

            if j==k:

                a.pop(0)

            else:j+=1

        return False

print(Solution().containsNearbyDuplicate([1,2,3,1],3))

print(Solution().containsNearbyDuplicate([1,0,1,1],1))

print(Solution().containsNearbyDuplicate([1,2,3,1,2,3],2))

第1-3，15-17行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第4行： 定义空列表a用于存放nums中的元素

第5行： 定义变量i,j,b分别赋值0,0和nums列表的长度

第6行： 当i小于列表长度时，执行循环

第7行： 判断nums中索引为i的元素是否在列表a中，若在，则返回true

第8-9行： 若不在，则在列表中添加该元素，并令索引i加一

第10行： 判断此时列表a长度是否小于k

第11行： 若等于k，则需要删除a窗口第一个元素

第12行： 若不等于k则小于k，则令j加一代表窗口长度加一

第13行： 若一直未返回True，则没有满足题意的，返回False

代码运行结果为：

算法讲解

这里用到了基础技巧：滑动窗口，简单讲解下这个技巧：

什么是滑动窗口

滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。

可以想象成队列，一端在push元素，另一端在pop元素，如下所示：

假设有数组[a b c d e f g h]

一个大小为3的滑动窗口在其上滑动,则有:

[a b c]

  [b c d]

    [c d e]

      [d e f]

        [e f g]

          [f g h]

适用范围

- 1、一般是字符串或者列表

- 2、一般是要求最值（最大长度，最短长度等等）或者子序列

算法思想

- 1、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。

- 2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。

- 3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。

- 4、重复第 2 和第 3 步，直到 right 到达序列的尽头。

思路其实很简单：第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

如果你想用Python开辟副业赚钱，但不熟悉爬虫与反爬虫技术，没有接单途径，也缺乏兼职经验
关注下方微信公众号：Python编程学习圈，获取价值999元全套Python入门到进阶的学习资料以及教程，还有Python技术交流群一起交流学习哦。