存在重复元素 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" false < code></=k:>
存在重复元素 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： 3： 输出：false code></=t>
有 abs(i-j)=k可知，窗口大小为 k+1时，窗口内的元素索引差都会小于 k,然后在用新增的元素与窗口内的其他元素进行比较差值是否满足 abs(nums[i]-nums[j])<=t< code>即可<!--=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</=t,可知窗口的大小为k+1>
可是在提交测试时，显示超时，时间复杂度len(nums)*k，显然滑动窗口的解法不合适，那使用桶排序吧
桶排序的思路：因为差值为 t，所以需要 t+1个桶，则桶内每个元素的差值都 <=t< code>,如果当前桶内没有元素，则往前一个桶查找，如果有值，并且<code><=u-t< code>，或者往下一个桶找，并且<code>>=u+t</code>为满足条件，并且k去维护桶的总个数<!--=u-t<--></code><!--=t<-->
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
</=v+t:>
长度最小的子数组
给定一个含有 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
</=right></n:>
无重复字符的最长子串
给定一个字符串 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 < code></right:>
滑动窗口最大值
`
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
Original: https://www.cnblogs.com/hitechr/p/15120088.html
Author: Hitechr
Title: 【每日算法】算法复习一
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/590441/
转载文章受原作者版权保护。转载请注明原作者出处！