[HOT 100] 0003. 无重复字符的最长子串

文章目录

      • 1. 题目链接
      • 2. 题目描述
      • 3. 题目示例
      • 4. 解题思路
      • 5. 题解代码
      • 6. 复杂度分析

1. 题目链接


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


2. 题目描述


给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。



3. 题目示例


示例 1 :

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2 :

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

4. 解题思路


1. 初始化数据结构:

  • ans:存储结果的列表,用来保存所有符合条件的起始位置。
  • cntP:长度为 26 的数组,记录字符串 p 中每个字母的出现次数。这里假设字符串中的字符均为小写字母。
  • cntS:长度为 26 的数组,记录当前窗口(即字符串 s 中一个子串)中每个字母的出现次数。

2. 统计 **p** 中字符的频次:

for (char c : p.toCharArray()) {cntP[c - 'a']++;
}

遍历字符串 p,根据每个字符的 ASCII 码值统计其出现次数。c - 'a' 将字母转化为数组下标(例如:'a' 对应下标 0'b' 对应下标 1,依此类推)。


3. 滑动窗口遍历字符串 **s**

for (int right = 0; right < s.length(); right++) {cntS[s.charAt(right) - 'a']++; // 右端点字母进入窗口int left = right - p.length() + 1;if (left < 0) { // 窗口长度不足 p.length()continue;}if (Arrays.equals(cntS, cntP)) { // s' 和 p 的每种字母的出现次数都相同ans.add(left); // s' 左端点下标加入答案}cntS[s.charAt(left) - 'a']--; // 左端点字母离开窗口
}
  • **右指针 ****right**:从 0 遍历到 s.length() - 1,表示当前窗口的右端。
  • **cntS[s.charAt(right) - 'a']++**:每次右指针移动时,更新窗口中的字符频次。
  • **计算左指针 ****left**left = right - p.length() + 1,计算窗口的左边界。如果窗口的长度小于 p.length()(即 left 小于 0),就跳过当前迭代,继续移动右指针。
  • 判断是否为异位词Arrays.equals(cntS, cntP) 比较当前窗口内字符的频次与字符串 p 的字符频次是否相同。如果相同,则说明找到了一个异位词子串,将其左端点 left 加入结果 ans
  • 左指针字母离开窗口:在每次遍历结束时,更新 cntS 数组,移除左端字符的频次:cntS[s.charAt(left) - 'a']--

5. 题解代码


class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> ans = new ArrayList<>();int[] cntP = new int[26]; // 统计 p 的每种字母的出现次数int[] cntS = new int[26]; // 统计 s 的长为 p.length() 的子串 s' 的每种字母的出现次数for (char c : p.toCharArray()) {cntP[c - 'a']++; // 统计 p 的字母}for (int right = 0; right < s.length(); right++) {cntS[s.charAt(right) - 'a']++; // 右端点字母进入窗口int left = right - p.length() + 1;if (left < 0) { // 窗口长度不足 p.length()continue;}if (Arrays.equals(cntS, cntP)) { // s' 和 p 的每种字母的出现次数都相同ans.add(left); // s' 左端点下标加入答案}cntS[s.charAt(left) - 'a']--; // 左端点字母离开窗口}return ans;}
}

6. 复杂度分析


  • 时间复杂度: 遍历字符串 s 一次,时间复杂度为 O(n),其中 n 是字符串 s 的长度。

  • 在每次窗口滑动时,Arrays.equals(cntS, cntP) 的比较复杂度为 O(26),即常数时间。

  • 所以,总的时间复杂度是 O(n)

  • 空间复杂度: cntPcntS 都是长度为 26 的数组,因此空间复杂度为 O(1)(常数空间)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/10141.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数据分析系列--⑤RapidMiner进行关联分析(中文数据案例)

一、数据集 二、数据预处理 1.读取数据、拆分、重命名 2.数据预处理 三、关联分析 四、结论 一、数据集 点击下载数据集shopping_basket.xlsx ,这个数据集专门使用中文数据来进行分析. 二、数据预处理 1.读取数据、拆分、重命名 2.数据预处理 三、关联分析 四、结论 Ok,E…

拦截器快速入门及详解

拦截器Interceptor 快速入门 什么是拦截器&#xff1f; 是一种动态拦截方法调用的机制&#xff0c;类似于过滤器。 拦截器是Spring框架中提供的&#xff0c;用来动态拦截控制器方法的执行。 拦截器的作用&#xff1a;拦截请求&#xff0c;在指定方法调用前后&#xff0c;根…

PythonFlask框架

文章目录 处理 Get 请求处理 POST 请求应用 app.route(/tpost, methods[POST]) def testp():json_data request.get_json()if json_data:username json_data.get(username)age json_data.get(age)return jsonify({username: username测试,age: age})从 flask 中导入了 Flask…

134.力扣刷题--加油站--滑动窗口

你知道的&#xff0c;失败总是贯穿人生的始终。 加油站 在一条环路上有 n 个加油站&#xff0c;其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车&#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发&#x…

大数据学习之Kafka消息队列、Spark分布式计算框架一

Kafka消息队列 章节一.kafka入门 4.kafka入门_消息队列两种模式 5.kafka入门_架构相关名词 Kafka 入门 _ 架构相关名词 事件 记录了世界或您的业务中 “ 发生了某事 ” 的事实。在文档中 也称为记录或消息。当您向 Kafka 读取或写入数据时&#xff0c;您以事件的 形式执行…

书生大模型实战营5

文章目录 L1——基础岛书生大模型全链路开源开放体系概览书生大模型全链路的数据书生大模型全链路的开源数据处理工具箱预训练 InterEvo微调 XTunerOpenCompass 评测体系部署 LMDeploy智能体 Lagent智能体 MindSearchHuixiangDou L1——基础岛 书生大模型全链路开源开放体系 …

Deepseek技术浅析(二):大语言模型

DeepSeek 作为一家致力于人工智能技术研发的公司&#xff0c;其大语言模型&#xff08;LLM&#xff09;在架构创新、参数规模扩展以及训练方法优化等方面都达到了行业领先水平。 一、基于 Transformer 架构的创新 1.1 基础架构&#xff1a;Transformer 的回顾 Transformer 架…

leetcode——对称二叉树(java)

给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true 示例 2&#xff1a; 输入&#xff1a;root [1,2,2,null,3,null,3] 输出&#xff1a;false 解题方法&#xff1a;&#xff08…

Spring Boot 日志:项目的“行车记录仪”

一、什么是Spring Boot日志 &#xff08;一&#xff09;日志引入 在正式介绍日志之前&#xff0c;我们先来看看上篇文章中&#xff08;Spring Boot 配置文件&#xff09;中的验证码功能的一个代码片段&#xff1a; 这是一段校验用户输入的验证码是否正确的后端代码&#xff0c…

android 圆形弹窗摄像头开发踩坑——源码————未来之窗跨平台操作

一、飘窗刷脸&#xff0c;拍照采用飘窗 刷脸认证安卓接口采用飘窗具有在不干扰用户主要操作的前提下以醒目方式引导用户完成认证&#xff0c;且能灵活定制样式以提升用户体验和认证效率的优点 二、踩坑只有一个扇形 <?xml version"1.0" encoding"utf-8&quo…

DeepSeek的崛起与全球科技市场的震荡

引言 近年来&#xff0c;人工智能&#xff08;AI&#xff09;技术的快速发展不断重塑全球科技格局。 近日&#xff0c;中国初创企业DeepSeek推出了一款据称成本极低且性能强大的AI模型&#xff0c;引发全球市场的剧烈反应。NVIDIA、台积电等半导体和AI科技巨头股价大幅下跌&am…

单机伪分布Hadoop详细配置

目录 1. 引言2. 配置单机Hadoop2.1 下载并解压JDK1.8、Hadoop3.3.62.2 配置环境变量2.3 验证JDK、Hadoop配置 3. 伪分布Hadoop3.1 配置ssh免密码登录3.2 配置伪分布Hadoop3.2.1 修改hadoop-env.sh3.2.2 修改core-site.xml3.2.3 修改hdfs-site.xml3.2.4 修改yarn-site.xml3.2.5 …

大数据相关职位 职业进阶路径

大数据相关职位 & 职业进阶路径 &#x1f4cc; 大数据相关职位 & 职业进阶路径 大数据领域涵盖多个方向&#xff0c;包括数据工程、数据分析、数据治理、数据科学等&#xff0c;每个方向的进阶路径有所不同。以下是大数据相关职位的详细解析及其职业进阶关系。 &#…

《大语言模型》综述学习笔记

《A Survey of Large Language Models》英文版综述最近出了中文版书——《大语言模型》&#xff0c;本博客作为阅读笔记记录一下&#xff0c;综述主页&#xff1a;https://github.com/RUCAIBox/LLMSurvey 关于LLM的一些概述和理解 记录一些有启发性的说法&#xff1a; 1、当前…

供应链系统设计-供应链中台系统设计(十二)- 清结算中心设计篇(一)

概述 在之前的文章中&#xff0c;我们通过之前的两篇文章中&#xff0c;如下所示&#xff1a; 供应链系统设计-供应链中台系统设计&#xff08;十&#xff09;- 清结算中心概念片篇 供应链系统设计-供应链中台系统设计&#xff08;十一&#xff09;- 清结算中心概念片篇 说…

MySQL查询优化(三):深度解读 MySQL客户端和服务端协议

如果需要从 MySQL 服务端获得很高的性能&#xff0c;最佳的方式就是花时间研究 MySQL 优化和执行查询的机制。一旦理解了这些&#xff0c;大部分的查询优化是有据可循的&#xff0c;从而使得整个查询优化的过程更有逻辑性。下图展示了 MySQL 执行查询的过程&#xff1a; 客户端…

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】1.26 统计圣殿:从描述统计到推断检验

1.26 统计圣殿&#xff1a;从描述统计到推断检验 目录 #mermaid-svg-3nz11PRr47fVfGWZ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3nz11PRr47fVfGWZ .error-icon{fill:#552222;}#mermaid-svg-3nz11PRr47fVfGWZ…

如何用 Groq API 免费使用 DeepSeek-R1 70B,并通过 Deno 实现国内访问

这几天都被Deepseek刷屏了&#xff0c;而且Deepseek由于异常访问量&#xff0c;这几天都不能愉快的和它玩耍了&#xff0c; 我发现Groq新增了一个Deepseek的70b参数的模型&#xff0c; DeepSeek-R1 70B 作为一款强大的开源模型&#xff0c;提供了卓越的推理能力&#xff0c;而 …

物联网智能项目之——智能家居项目的实现!

成长路上不孤单&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a;&#x1f60a; 【14后&#x1f60a;///计算机爱好者&#x1f60a;///持续分享所学&#x1f60a;///如有需要欢迎收藏转发///&#x1f60a;】 今日分享关于物联网智能项目之——智能家居项目…

Linux《基础指令》

在之前的Linux《Linux简介与环境的搭建》当中我们已经初步了解了Linux的由来和如何搭建Linux环境&#xff0c;那么接下来在本篇当中我们就要来学习Linux的基础指令。在此我们的学习是包括两个部分&#xff0c;即指令和关于Linux的基础知识&#xff1b;因此本篇指令和基础知识的…