滑动窗口与双指针

灵神题单：分享丨【算法题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）- 讨论 - 力扣（LeetCode）

场景：连续、遍历各情况

尚未分类

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # #遍历 
        # for i in range(len(nums)-1):
        #     for j in range(i+1,len(nums)):
        #         if nums[i]+nums[j]==target: 
        #             return [i,j]

        # 哈希表  python 字典最好 键不存在即0个，但是要存索引 
        dic=dict()
        for i,e in enumerate(nums):
            # if dic.get(target-e) is not None:
            # in方法就是用的哈希表查找  
            if target-e in dic:
                return [dic[target-e], i]
            dic[e]=i

what I learn

哈希表的查找用in方法可实现，用dict()或set()最好，用空间换时间。
集合、字典的 in 方法时间复杂度O(1)，列表和元组的 in 时间复杂度O(n)。

删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
- 返回 k 。
示例

1
2
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:

        # 哈希表  空间换时间

        # dic=set()
        # for e in nums:
        #     if e not in dic:
        #         dic.add(e)
        #         nums[len(dic)-1]=e
        #         # print(dic)
        #         # print(nums)
        #         # print("----")
        # return len(dic)

        # 双指针  利用有序性
        
        p=0
        for e in nums:
            if e!=nums[p]:
                p+=1
                nums[p]=e

        return p+1

what I learn

快慢指针，数据需要有有序性。

搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

**（二分法）**记住就好了 T-T
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例：

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 上下界限设置，target 最大时要放在“第len(nums)个位置”，最小时要放在“第0个位置”
        up=len(nums)
        low=0
        
        while(True):
            # i为 正中（奇）或 偏上（偶）
            i=(low+up)//2
            # 重合即为最终位置
            if low==up:
                return low
            # 因为是向下取整的i，上界下移到i;下界上移到i+1。
            # 比如low=0,up=5，则：mid=2.5,i=2，小的区域为0~2(i)，大的区域为3(i+1)~5
            if target<nums[i]:
                up=i
            elif target>nums[i]:
                low=i+1
            else:
                return i

what I learn

二分法框架：
- 上下界up=len(nums) low=0
- 取中间(low+up)//2
- 终止条件 low==up
- 上界降 up=mid
- 下界升 low=mid+1

加一

66. 加一 - 力扣（LeetCode）

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：

1
2
3
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

1
2
3
4
5
输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # 逆序，从低位开始，发现小于9的说明不用进位，加一退出，否则+1是10，当前位为0，进入下一位重复
        for i in range(len(digits)-1,-1,-1):
            if digits[i]<9:
                digits[i]+=1
                break
            digits[i]=0
		# 如果最高位为0，说明进位了，前面插入1
        if not digits[0]:
            digits.insert(0,1)
        return digits

what I learn

逆序索引 range(len(digits)-1,-1,-1) 从len(digits)-1开始，步长为-1(递减)，到-1，左闭右开[len(digits)-1, -1)。

定长滑动窗口

共性在于“一进一出”
记录变化计算、设置、边界值处理
逆向、排序、分组等特殊处理

半径为 k 的子数组平均值

2090. 半径为 k 的子数组平均值 - 力扣（LeetCode）

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。
半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为中心且半径为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。
构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。
例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

1
2
输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:        
        # 我老想着动态得去判断加-1进result列表
        avgs = [-1] * len(nums)
        s = 0  # 维护窗口元素和
        for i, x in enumerate(nums):
            # 1. 进入窗口
            s += x
            if i < k * 2:  # 窗口大小不足 2k+1
                continue
            # 2. 记录答案
            avgs[i - k] = s // (k * 2 + 1)
            # 3. 离开窗口
            s -= nums[i - k * 2]
        return avgs
# 作者-灵神

what I learn

观察问题的本质，不要被方法带着走。
- 问题的本质：待到要处理的索引时，得出平均值放入数组。
- 方法带偏：想着边遍历边append，开头去append -1，结束了再补充-1。
- 解决的关键：初始化nums长度的 -1数组，即 [-1] * len(nums)。

几乎唯一子数组的最大和

2841. 几乎唯一子数组的最大和 - 力扣（LeetCode）

给你一个整数数组 nums 和两个正整数 m 和 k 。
请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
子数组指的是一个数组中一段连续非空的元素序列。
示例

1
2
3
输入：nums = [2,6,7,3,1,7], m = 3, k = 4
输出：18
解释：总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        sum_n = max_sum = 0
        dif_n=defaultdict(int)

        for i, element in enumerate(nums):
            dif_n[element] += 1
            sum_n += element
            
            left = i-k+1			
            if left < 0:
                continue

            if len(dif_n) >= m:
                max_sum = max(sum_n,max_sum)

            out=nums[left]
            sum_n -= out
            dif_n[out] -= 1
            if dif_n[out] == 0:
                del dif_n[out]
			
        return max_sum

what I learn

sum_n = max_sum = 0
使用defaultdict
- 默认值为0，dif_n=defaultdict(int) 因为int()返回0（不如Counter）
- if dif_n[out] == 0: del dif_n[out] 删除其中值为0的键值对
max_sum = max(sum_n,max_sum) 而不用 if 条件判断
left = i-k+1 …. out=nums[left] 使代码更简洁美观

找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

what I learn

Counter

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from collections import Counter

# 示例 1：统计字母频次
cnt_p = Counter("aabbc") 
print(cnt_p)  # 输出：Counter({'a': 2, 'b': 2, 'c': 1})

# 示例 2：访问不存在的键
print(cnt_p["d"])  # 输出：0（不会报错！）

# 改变值，类似字典
cnt_p["a"]+=1

# 比较和集合操作
cnt_1 = Counter("bcd") 
cnt_2 = Counter("abc") 
print(cnt_1==cnt2)
print(cnt_1-cnt_2)
print(cnt_1+cnt_2)