分享｜从TOP100学习算法 ③ 字符串，数组，序列？
Q萝A卜Q
355
2024.11.28
2024.11.28
发布于 中国
刷题交流学习分享

按照顺序应该是刷到子串的相关题目了
子串跟字符串相关联，我其实也顺便提点字符串吧

  1. 简介
  2. 预备知识
  3. 例题
  4. 动手试试和进阶知识
  5. 现实中的应用
  6. 想说的话

简介

字符串,可以算是字符组成的数组
或者说 就是由字符连接而成的序列
后面的题目是既包括数组也包括字符串，可能数组和字符串语法上有点区别
数组可以是二维的甚至更高
但是我觉得本质上都是一个序列，满足一定的顺序条件
那么稍微严谨一点

我想我们刚开始的时候就接触了

JavaScript
Python
Ruby
C
c++
Java
console.log('Hello world!')

Hello world!就是字符串（我不说你们也知道😀）

子串：字符串 S 的 子串 ，S[i..j]，i≤j，表示 S 串中从 i 到 j 这一段，也就是顺次排列起来，得到S的子串

比如 “llo”是“Hello”的子串，不能拆开，要连在一起

区分一下子序列：字符串 S 的 子序列 是从 S 中将若干元素提取出来并不改变相对位置形成的序列，即

举例子来说 “Heo”是“Hello”的子序列，这个不需要连在一起

预备知识

了解一下哈希表（没有了解可以先看看数据结构）

还有前后缀，还是hello举例子
后缀 是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。 “llo”是后缀

前缀 是指从串首开始到某个位置 i 结束的一个特殊子串。 “hel”是前缀

例题

还是按照力扣热题100的顺序，和为 K 的子数组

和为 K 的子数组

和为 K 的子数组-官方题解

利用前缀的和，还有哈希表可以方便的解决,那就用官方题解的例子讲解一下

给出数组 nums= [3,4,7,2,-3,1,4,2] 目标和k=7
创建一个哈希表map 它的键是前缀和，它的值为出现这个前缀和次数
pre代表前缀和
count 代表我们找到了满足条件的和，然后我们计数

那我们为什么要使用pre-k呢？
pre-k就代表 前缀和-目标值 就是说前缀和 离目标值的距离
从之前哈希表存过那个点到当前点的子数组之和恰好是 k
image.png

以官解中的例子，4的时候我们存过一次{7,1} 当我们遍历到1的时候 pre为14
Pre-k=7,出现过在之前的map中，那就意味着

即14-7=7
那就意味着我们找到了满足目标值的子数组了，map显示出现过一次，那我们count就+1
image.png

再举个例子
nums=[1,1,1,3,2] k=4

image.png
遍历到3的时候前缀和是6 ，这时我们的前缀和离目标值 pre-k = 2 （我们的前缀和与目标值只相差2）
我们发现之前前缀和已经是2（以前存在map当中）
所以当前数组要凑成目标值，只需要把前面那部分[1,1]不要就好，那么1+3就凑成目标值4了
pre-（pre-k）=1+1+1+3 - （1+1）=4 （满足目标值）
在搞清楚前缀离目标值距离这个关键要素之后，我们可以展示一下官解中的过程了


***

回到官方例子中nums= [3,4,7,2,-3,1,4,2] 目标和 k=7

再次说明一下
哈希表map 它的键是前缀和，它的值为出现这个前缀和次数
pre代表前缀和
count 代表我们找到了满足条件的和，然后我们计数
pre-k 代表前缀和离目标值的距离

<image.png{:width=400},image.png{:width=400},image.png{:width=400},image.png{:width=400},image.png{:width=400},image.png{:width=400},image.png{:width=400},image.png{:width=400},image.png{:width=400}>

(windows画图+windows自带截图软件截的图，手画还是麻烦了点。而且在力扣markdown编辑器，幻灯片要9个图片全部放在一行，让我想起了bootstrap的压缩版代码)😶

下面我们把动画的思路整理成代码，现在看看吧

Python
class Solution:  
    def subarraySum(self, nums: list[int], k: int) -> int:  
        # 初始化一个字典，用于存储前缀和及其出现的次数，初始时前缀和为0的次数为1
        # 这是因为前缀和为0可以认为是一个空子数组的和，对于计算有帮助
        mp = {0: 1}  
        
        # 初始化计数器，用于记录满足条件的子数组个数
        count = 0  
        
        # 初始化前缀和变量
        pre = 0  
          
        # 遍历数组中的每个元素
        for x in nums:  
            # 更新当前的前缀和
            pre += x  
            
            # 检查是否存在一个之前的前缀和，使得当前前缀和减去这个之前的前缀和等于k
            # 如果存在，说明从那个前缀和到当前前缀和之间的子数组的和为k
            # 因此，将满足条件的子数组个数增加之前前缀和出现的次数（因为可能存在多个相同的前缀和）
            if pre - k in mp:  
                count += mp[pre - k]  
            
            # 更新当前前缀和出现的次数
            # 如果当前前缀和已经存在于字典中，则将其次数加1
            # 如果不存在，则将其添加到字典中，次数初始化为1
            mp[pre] = mp.get(pre, 0) + 1  
          
        # 返回满足条件的子数组个数
        return count

动手试试和进阶知识

可以了解一下滑动窗口，队列等
感兴趣可以了解
稀疏表(Sparse Table) , 利用前缀的KMP算法，利用后缀的Boyer–Moore算法，常用于字典查询的字典树(Trie)等
可以参考oi wiki网站

动手试试吧
滑动窗口最大值

最小覆盖子串

现实中的应用

字符串算法，像kmp算法用于字符串搜索，字典树应用于 词频统计
(图片来源于网络，必应图片)

<image.png{:width=400},image.png{:width=400}>

除了常见的搜索算法，在深度学习自然语言处理中，文本序列放到编码器和解码器中 就可以实现输出序列的预测
image.png
（图片来源于动手学深度学习）

想说的话

已经入职几个月了，变得更加佛系随缘了😂
之后更新可能看情况，关于这个热题100，关于常见的数据结构我应该会跳过
比如数组，二叉树，图这些
这些知识点我觉得参考看数据结构就可以了（我上大学时候用的数据结构（c语言）严蔚敏教授那个版本
现在我感觉还是hello算法那种生动有趣点，不知道友友们有无推荐？）

我个人比较偏向于写算法和解法那类的，还有关心实际生活应用

接下来可能写回溯，贪心和动态规划？

评论 (1)