阳江市网站建设_网站建设公司_定制开发_seo优化

LeetCode 100天挑战 Day 3：判断子序列与汇总区间

目录

• 前言
• 题目一：判断子序列问题
  • 题目描述
  • 解题思路
  • 代码实现分析
  • 复杂度分析
  • 进阶优化：批量处理方案
• 题目二：汇总区间问题
  • 题目描述
  • 解题思路
  • 代码实现分析
  • 复杂度分析
  • 边界情况处理
• 算法思想对比与总结
• 实际应用场景
• 参考资源

---

前言

在算法学习的过程中，字符串处理和数组操作是两个非常重要的领域。今天的两道题目分别代表了这两个领域的经典问题：判断子序列问题考察我们对字符串匹配的理解，而汇总区间问题则训练我们对有序数组的处理能力。这两个问题虽然难度不同，但都蕴含着重要的算法思想。

今日题目统计信息

题目	难度	知识点	通过率	核心思想
判断子序列	简单	双指针、字符串匹配	52.1%	贪心算法
汇总区间	中等	数组遍历、区间合并	58.3%	一次遍历

---

题目一：判断子序列问题

题目描述

给定字符串 s 和 t，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。例如，"ace"是"abcde"的一个子序列，而"aec"不是。

进阶挑战：如果有大量输入的 S，称作 S1, S2, …, Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = "abc", t = "ahbgdc" 输出：true

示例 2：

输入：s = "axc", t = "ahbgdc" 输出：false

解题思路

这个问题的核心思想是贪心算法结合双指针技巧。我们需要在t中按顺序寻找s的每个字符：

1. 基础思路：

   • 使用两个指针，一个指向s的当前位置，一个指向t的当前位置
   • 在t中顺序查找s的当前字符
   • 找到后，s的指针向前移动，t的指针从找到位置的下一个位置继续查找
   • 如果s的所有字符都能在t中按顺序找到，则s是t的子序列

2. 优化考虑：

   • 如果s的长度大于t的长度，直接返回false
   • 如果s为空字符串，直接返回true
   • 如果s和t长度相等且内容相同，返回true

代码实现分析

classSolution{publicbooleanisSubsequence(Strings,Stringt){intlen1=s.length();intlen2=t.length();// 边界情况处理if(len1==0){returntrue;}if(len2==0){returnfalse;}if(len1==len2){returns==t;}// 主逻辑：双指针查找intindex=0;// t中的查找起始位置for(inti=0;i<len1;i++){if(index>=len2){returnfalse;// t已经遍历完但s还有字符未匹配}// 从index开始在t中查找s.charAt(i)for(intj=index;j<len2;j++){if(s.charAt(i)==t.charAt(j)){index=j+1;// 更新下次查找的起始位置break;}// 如果遍历到最后一个字符都没找到匹配if(j==len2-1){returnfalse;}}}returntrue;}}

代码逐行解析：

1. 长度获取与边界处理：

intlen1=s.length();intlen2=t.length();if(len1==0){returntrue;// 空字符串是任何字符串的子序列}if(len2==0){returnfalse;// 非空字符串不是空字符串的子序列}if(len1==len2){returns==t;// 长度相同时只有完全相等才是子序列}

2. 核心查找逻辑：

intindex=0;// 记录在t中查找的起始位置for(inti=0;i<len1;i++){// 遍历s的每个字符for(intj=index;j<len2;j++){// 在t中从index位置开始查找if(s.charAt(i)==t.charAt(j)){index=j+1;// 找到后更新下次查找位置break;}}}

复杂度分析

指标	分析过程	结果
时间复杂度	最坏情况下需要遍历整个t字符串	O(m×n)，其中m=len(s), n=len(t)
空间复杂度	只使用了常数个额外变量	O(1)

注意：虽然时间复杂度看起来是O(m×n)，但在实际运行中，由于t的指针不会回退，实际时间复杂度更接近O(m+n)。

进阶优化：批量处理方案

针对进阶挑战中提到的大量输入情况，我们需要对t进行预处理：

classSolution{// 预处理t，构建字符位置映射privateMap<Character,List<Integer>>preprocess(Stringt){Map<Character,List<Integer>>charPositions=newHashMap<>();for(inti=0;i<t.length();i++){charc=t.charAt(i);charPositions.computeIfAbsent(c,k->newArrayList<>()).add(i);}returncharPositions;}// 使用二分查找优化子序列检查publicbooleanisSubsequenceOptimized(Strings,Stringt){Map<Character,List<Integer>>charPositions=preprocess(t);intcurrentIndex=-1;for(charc:s.toCharArray()){if(!charPositions.containsKey(c)){returnfalse;}List<Integer>positions=charPositions.get(c);// 找到第一个大于currentIndex的位置intfoundIndex=Collections.binarySearch(positions,currentIndex+1);if(foundIndex<0){foundIndex=-foundIndex-1;}if(foundIndex==positions.size()){returnfalse;}currentIndex=positions.get(foundIndex);}returntrue;}}

优化方案分析：

方法	预处理时间	单次查询时间	适用场景
原始方法	O(1)	O(m+n)	单次查询
优化方法	O(n)	O(m×logk)	大量查询

---

题目二：汇总区间问题

题目描述

给定一个无重复元素的有序整数数组nums。

区间[a,b]是从a到b（包含）的所有整数的集合。

返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个区间但不属于nums的数字x。

输出格式要求：

• “a->b”，如果a != b
• “a”，如果a == b

示例 1：

输入：nums = [0,1,2,4,5,7] 输出：["0->2","4->5","7"]

示例 2：

输入：nums = [0,2,3,4,6,8,9] 输出：["0","2->4","6","8->9"]

解题思路

这个问题可以通过一次遍历解决，核心思想是识别连续的数字序列：

1. 主要思路：

   • 遍历数组，记录当前区间的起始位置
   • 检查当前数字与下一个数字是否连续
   • 如果不连续，结束当前区间并开始新的区间
   • 处理最后一个区间的特殊情况

2. 关键判断条件：

   • nums[i] + 1 != nums[i + 1]：当前数字与下一个数字不连续
   • i + 1 == nums.length：已到达数组末尾

代码实现分析

classSolution{publicList<String>summaryRanges(int[]nums){List<String>result=newArrayList<>();// 边界情况：空数组if(nums.length==0){returnresult;}intstart=0;// 当前区间的起始位置for(inti=0;i<nums.length;i++){// 判断是否需要结束当前区间if(i+1==nums.length||nums[i]+1!=nums[i+1]){if(start==i){// 单个数字的区间result.add(String.valueOf(nums[start]));}else{// 多个数字的连续区间result.add(nums[start]+"->"+nums[i]);}start=i+1;// 开始新区间}}returnresult;}}

代码详细解析：

1. 初始化与边界处理：

List<String>result=newArrayList<>();if(nums.length==0){returnresult;// 空数组直接返回空列表}

2. 核心遍历逻辑：

intstart=0;// 记录当前区间的起始索引for(inti=0;i<nums.length;i++){// 检查区间结束条件if(i+1==nums.length||nums[i]+1!=nums[i+1]){// 处理区间结束}}

3. 区间格式化逻辑：

if(start==i){// 单个元素区间result.add(String.valueOf(nums[start]));}else{// 多个元素的连续区间result.add(nums[start]+"->"+nums[i]);}start=i+1;// 更新下一个区间的起始位置

复杂度分析

指标	分析	结果
时间复杂度	只需要一次遍历	O(n)
空间复杂度	存储结果列表，最坏情况n个区间	O(n)

边界情况处理

让我们分析各种可能的输入情况：

边界情况详细分析

输入情况	处理方式	预期输出
空数组[]	直接返回空列表	[]
单元素[5]	单个元素的区间	["5"]
全连续[1,2,3,4]	整个数组作为一个区间	["1->4"]
全不连续[1,3,5,7]	每个元素单独成区间	["1","3","5","7"]
负数[-3,-2,-1,0]	包含负数的连续区间	["-3->0"]

---

算法思想对比与总结

共同特点分析

虽然这两道题目看似不同，但它们都体现了几个重要的算法思想：

1. 一次遍历原则：

   • 子序列问题：顺序查找，不回退
   • 区间汇总问题：线性扫描，动态分组

2. 边界条件处理：

   • 都需要仔细处理空输入等特殊情况
   • 都涉及循环结束条件的精确判断

3. 状态维护：

   • 子序列问题：维护当前查找位置
   • 区间汇总问题：维护当前区间起始位置

解题技巧总结

技巧	子序列问题应用	区间汇总问题应用
双指针	✅ 在t中顺序查找s的字符	✅ start和i形成区间边界
贪心算法	✅ 每次找到最早匹配的位置	✅ 尽可能扩展连续区间
状态机	✅ 维护查找状态	✅ 维护区间开始/结束状态
边界处理	✅ 多种特殊情况处理	✅ 数组边界和连续性判断

---

实际应用场景

判断子序列的应用

1. 文本搜索与匹配：

   • 搜索引擎的关键词匹配
   • 文本编辑器中的模式查找
   • 生物信息学中的DNA序列匹配

2. 数据验证：

   • 输入格式验证
   • 协议解析中的字段顺序检查
   • 版本兼容性检查

汇总区间的应用

1. 数据压缩：

   • 连续数字范围的压缩存储
   • 日志文件的压缩记录
   • 网络地址范围表示

2. 数据分析：

   • 时间序列数据的区间分析
   • 传感器数据的连续区间识别
   • 金融数据的连续涨跌区间统计

性能优化建议

// 子序列问题性能测试publicvoidperformanceTest(){Stringt="a".repeat(1000000)+"b".repeat(1000000);Strings="ab";longstartTime=System.currentTimeMillis();booleanresult=isSubsequence(s,t);longendTime=System.currentTimeMillis();System.out.println("结果: "+result+", 耗时: "+(endTime-startTime)+"ms");}// 区间汇总问题扩展测试publicvoidrangeSummaryExtended(){// 测试大数据量int[]largeArray=newint[1000000];for(inti=0;i<largeArray.length;i++){largeArray[i]=i*2;// 创建间隔为2的序列}List<String>result=summaryRanges(largeArray);System.out.println("结果数量: "+result.size());}

---

总结与思考

通过今天对这两个算法题的深入分析，我们可以得到以下几点重要启示：

算法思维的提升

1. 问题抽象能力：

   • 将具体问题抽象为算法模型
   • 识别问题的核心本质
   • 选择合适的算法策略

2. 代码实现技巧：

   • 边界条件的重要性
   • 状态维护的方法
   • 代码可读性与效率的平衡

3. 优化思考方式：

   • 从暴力解法到最优解的思考路径
   • 时间复杂度与空间复杂度的权衡
   • 实际应用场景对算法选择的影响

学习建议

1. 循序渐进：

   • 先理解基本思路
   • 再考虑优化方案
   • 最后思考扩展应用

2. 举一反三：

   • 总结通用的解题模式
   • 建立知识间的联系
   • 培养算法直觉

3. 实践验证：

   • 编写代码验证思路
   • 测试各种边界情况
   • 分析性能瓶颈

编程感悟：算法学习不仅是掌握解题技巧，更重要的是培养分析问题、解决问题的思维能力。每一道题目都是一个思维训练的机会，通过深入思考和优化，我们能够不断提升自己的编程水平。

---

参考资源

1. LeetCode官方题库 - 判断子序列
2. LeetCode官方题库 - 汇总区间
3. Java字符串处理官方文档
4. Java集合框架文档
5. 算法与数据结构学习指南
6. 二分查找算法详解
7. 贪心算法原理与应用

如果你觉得这篇文章对你有所帮助，欢迎点赞、收藏和关注！如有疑问或不同见解，欢迎在评论区交流讨论。

---

标签：#LeetCode #算法 #Java #字符串 #数组 #双指针 #贪心算法 #数据结构