目录
Hash
存在重复元素 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
思路
def containsNearbyDuplicate(nums, k):
#定义 一个map，去记录每个元素在数组中的索引
dic={}
for i,v in enumerate(nums):
if v in dic:
#判断 是否满足索引差的绝对值至多为 k
# print(dic[v],i,dic[v]-i)
if i-dic[v]<=k:
return True
dic[v]=i
return False
存在重复元素 III
题目
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i]-nums[j])<=t ，同时又满足abs(i-j) <= k 。
如果存在则返回 true，不存在返回 false。
示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
思路
有abs(i-j)=k可知，窗口大小为k+1时，窗口内的元素索引差都会小于k,然后在用新增的元素与窗口内的其他元素进行比较差值是否满足abs(nums[i]-nums[j])<=t即可
def containsNearbyAlmostDuplicate(nums, k, t):
#abs(i-j)<=t,可知窗口的大小为k+1
q=collections.deque()
# print(q)
for i,v in enumerate(nums):
q.append(i)
#如果超过窗口的最大值，则移除左左侧的元素
if len(q)>k+1:
q.popleft()
for j in q:
if j<i and abs(nums[j]-nums[i])<=t:
return True
return False
可是在提交测试时，显示超时，时间复杂度len(nums)*k，显然滑动窗口的解法不合适，那使用桶排序吧
桶排序的思路：因为差值为t，所以需要t+1个桶，则桶内每个元素的差值都<=t,如果当前桶内没有元素，则往前一个桶查找，如果有值，并且<=u-t，或者往下一个桶找，并且>=u+t为满足条件，并且k去维护桶的总个数
def containsNearbyAlmostDuplicate(nums, k, t):
def getIdx(u):
return u//(t+1)
buckets={}#定义一个集合
for i,v in enumerate(nums):
# print(buckets)
idx=getIdx(v)#找到该元素数据哪个桶
#如果集合中保存这个元素,则满足条件直接返回
if idx in buckets:
return True
#找上一个，下一个桶
if idx-1 in buckets and buckets[idx-1]>=v-t:
return True
if idx+1 in buckets and buckets[idx+1]<=v+t:
return True
#保存当前元素
buckets[idx]=v
if len(buckets)>k:
buckets.pop(getIdx(nums[i-k]))
return False
滑动窗口
长度最小的子数组
题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
输入：target = 4, nums = [1,4,4]
输出：1
思路
使用可变的窗口，首先扩大窗口，使窗口内的总和扩大，当出现和>=target时，记录窗口左右边界的值，然后再缩小窗口，直到小于target时，在记录左右边界，并与之前比较，记录最小的那个；然后在重复上面的步骤，直到数组结尾。
def minSubArrayLen(target, nums):
#分别记录左右边界，和窗口内和
left,right,total=0,0,0
res=(left,float('inf'))
n=len(nums)
while right<n:
total+=nums[right]
if total>=target:#总和大于等于target时
#左移左边界
while left<=right and total>=target:
#记录左右边界
if res[1]-res[0]>right-left:
res=(left,right)
total-=nums[left]
left+=1
right+=1
return 0 if res[1]>n else res[1]-res[0]+1
无重复字符的最长子串
题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
思路
依然使用双指针的方式定义窗口的左右边界，使用hash来保存窗口内的元素，当新元素在hash里面的话，移动左边界并逐步删除hash里面的元素，直到不存在重复的元素位置，并计算dic的长度
import collections
def lengthOfLongestSubstring(s):
dic={}#保存窗口内的元素
left=0#左右移动的窗口
n=len(s)
res=0#最后的结果
q=collections.deque()
for right in range(n):
c=s[right]
#如果在窗口里面，从左到右逐个判断是否相等，相等则删除
while c in dic and left<right:
dic.pop(s[left])
left+=1
dic[c]=right
res=max(res,len(dic))
return res
滑动窗口最大值
题目
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,-1], k = 1
输出：[1,-1]
示例 4：
输入：nums = [9,11], k = 2
输出：[11]
示例 5：
输入：nums = [4,-2], k = 2
输出：[4]
思路
使用一个递减队列保存里面的元素，队列的头和尾的元素差小于k就是保证窗口的大小，因为是递减的，最左侧的元素就是最大元素，新来一个元素，如果比队尾元素小则正常入队，如果比队尾元素大，则从队尾删除，知道遇到一个比自己大，或空队列了，在加入队列中
import collections
def maxSlidingWindow(nums, k):
q=collections.deque()
res=[]#保存最后的结果
for i,v in enumerate(nums):
#新加入的元素和最后一个元素比较，如果小于则加入，如果大于从未到头逐个删除
while q and nums[q[-1]]<v:
q.pop()#删除最后一个
q.append(i)#加入新元素
# print("---")
while i>=k and q[0]<=i-k:#维护窗口的大小
q.popleft()#移除超出做边界的元素
# print(q,"===")
if i>=k-1:#当形成固定窗口后
res.append(nums[q[0]])
return res
最小覆盖子串
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
思路
依然使用双指针定义窗口的边界，逐渐扩大窗口，使其包括所有的t,然后在逐步缩小窗口，为了快速的判断是否包括所有的t，用一个tmp遍历记录t字符长度，用dic记录t中每个字符个数，当dic中存在，且字符个数大于0时，则tmp-1，并从dic中减小字符个数,当tmp=0时，就是找到了包含t中全部的字符了。
def minWindow(s, t):
left,right=0,0#窗口的边界
#记录字符串t中每个字符的个数
need=collections.defaultdict(int)
for c in t:
need[c]+=1
tmp=len(t)#是否找到全部的标记
n=len(s)
res=(0,float('inf'))
while right<n:
if need[s[right]]>0:
tmp-=1
need[s[right]]-=1
# print(tmp)
if tmp==0:#如果找到了全部的字符，左移left
#need[s[left]]<0为不在字符t中的字符
while left<right and need[s[left]]<0:
need[s[left]]+=1
left+=1#左移
#此时的left和right是包含t的最小字符串
if res[1]-res[0]>right-left:
res=(left,right)
#找到在字典中的字符位置
# print(need,tmp)
need[s[left]]+=1
tmp+=1
left+=1
# print(need,tmp)
right+=1
# print(res)
return "" if res[1]>len(s) else s[res[0]:res[1]+1]