Java字符串算法核心攻略

Java字符串算法核心攻略

提示：在 ASCII 码（美国信息交换标准代码）中，大小写英文字母和数字的十进制数值范围如下：

• 大写字母 (A - Z)：65 到 90
  • ‘A’ 是 65
  • ‘Z’ 是 90
• 小写字母 (a - z)：97 到 122
  • ‘a’ 是 97
  • ‘z’ 是 122
• 数字是 (0-9):48 到 57
  • ‘0’ 是 48
  • ‘9’ 是 57

一、必会的字符串方法

刷题前先把这些方法练熟，后面会反复用到。

1. 基础操作

String s ="hello"; s.length()// 5 - 获取长度，不是length，必须要加()。 s.charAt(0)// 'h' - 获取指定位置字符，传参传的是下标，从0开始 s.substring(1,4)// "ell" - 截取子串[1,4) s.indexOf('l')// 2 - 查找字符首次出现位置 s.contains("ell")// true - 是否包含子串 s.equals("hello")// true - 比较内容（别用==）

2. 字符串与数组互转

// String → char[]（需要修改字符串时用）char[] chars = s.toCharArray();// char[] → StringString s2 =newString(chars);// String → String[]（分割）String[] arr ="a,b,c".split(",");// ["a", "b", "c"]// String[] → String（拼接）String s3 =String.join(",", arr);// "a,b,c"

3. StringBuilder（循环拼接必用）

// 错误：循环里用+拼接，每次都创建新对象，超级慢String s ="";for(int i =0; i <10000; i++){ s +="a";// O(n²)}// 正确：用StringBuilderStringBuilder sb =newStringBuilder();for(int i =0; i <10000; i++){ sb.append("a");// O(n)}String result = sb.toString();

4. 字符判断

char c ='a';Character.isDigit(c)// 是否数字Character.isLetter(c)// 是否字母Character.isLetterOrDigit(c)// 判断是否是字母或数字Character.isLowerCase(c)// 是否小写Character.toLowerCase(c)// 转小写'5'-'0'// 5 - 字符转数字

5. 大小写转换与清理

String s =" Hello World "; s.toLowerCase()// " hello world " - 全转小写（判断回文串必用） s.toUpperCase()// " HELLO WORLD " - 全转大写 s.trim()// "Hello World" - 去掉首尾空格（处理输入必用） s.replaceAll("\\s+","")// "HelloWorld" - 去掉所有空格（正则替换）

6. 高级查找与匹配

String s ="hello world"; s.indexOf("world",6)// 6 - 从指定下标开始查找 s.lastIndexOf('l')// 9 - 查找字符最后一次出现位置 s.startsWith("he")// true - 是否以...开头 s.endsWith("ld")// true - 是否以...结尾 s.matches("[a-z]+")// true - 正则匹配（判断是否纯字母等）

7. 字符数组的高级操作

char[] chars ={'h','e','l','l','o'};// 数组排序（解决“有效的字母异位词”等题目必用）java.util.Arrays.sort(chars);// 数组转字符串后再比较String sorted =newString(chars);// 比较两个字符数组是否相等（比转String快）java.util.Arrays.equals(chars1, chars2);

8. 频率统计神器（HashMap/数组）

// 方法A：使用数组统计（仅限ASCII字符，速度最快 O(1)空间）int[] count =newint[128];// 覆盖所有ASCII码 count['a']++;// 直接利用char自动转int特性 count[c]--;// 抵消计数// 方法B：使用HashMap统计（支持Unicode/中文，通用但稍慢）java.util.Map<Character,Integer> map =newjava.util.HashMap<>(); map.put(c, map.getOrDefault(c,0)+1);// 计数+1 map.get(c);// 获取某个字符出现的次数 map.containsKey(c);// 判断是否包含该字符

9. 格式化输出（调试与构造必用）

// 类似 Python 的 f-string 或 C 的 printfString name ="Alice";int age =25;String info =String.format("Name: %s, Age: %d", name, age);// 结果："Name: Alice, Age: 25"// 常用占位符：// %s : 字符串// %d : 整数// %f : 浮点数// %c : 字符

二、字符串题型与解题思路

类型1：哈希表类（字符统计）

核心思想： 用空间换时间，快速查找和统计

什么时候用哈希表？

看到这些关键词就想到哈希表：

• 字符频次、出现次数
• 异位词、字母重排
• 第一个唯一字符
• 两个字符串的映射关系

模板：字符频次统计

// 模板1：HashMap统计（适用所有字符）publicMap<Character,Integer>countChars(String s){Map<Character,Integer> map =newHashMap<>();for(char c : s.toCharArray()){ map.put(c, map.getOrDefault(c,0)+1);// 频次+1}return map;}// 模板2：数组统计（仅小写字母，更快）publicint[]countCharsArray(String s){int[] count =newint[26];// 26个小写字母for(char c : s.toCharArray()){ count[c -'a']++;// 'a'映射到0，'b'映射到1...}return count;}

为什么数组比HashMap快？数组直接通过索引访问，HashMap需要计算哈希值。但数组只适用于字符集有限的情况（如26个字母）。

题目1：有效的字母异位词（LeetCode 242）

题目：判断两个字符串是否是异位词（字母相同但顺序不同）

输入: s = "anagram", t = "nagaram" 输出: true 输入: s = "rat", t = "car" 输出: false 

思路：异位词的特点是每个字符出现的次数相同，统计频次后比较即可。

publicbooleanisAnagram(String s,String t){// 1. 长度不同直接返回false（异位词长度必须相同）if(s.length()!= t.length())returnfalse;// 2. 创建数组统计26个小写字母的频次int[] count =newint[26];// 3. 遍历字符串s，统计每个字符出现的次数for(char c : s.toCharArray()){ count[c -'a']++;// 'a'映射到索引0，'b'映射到索引1...}// 4. 遍历字符串t，每遇到一个字符就将对应计数-1for(char c : t.toCharArray()){ count[c -'a']--;// 如果某个字符的计数变成负数，说明t中这个字符比s多if(count[c -'a']<0){returnfalse;}}// 5. 如果所有字符频次都匹配（都为0），则是异位词returntrue;}

为什么这样思考？如果两个字符串是异位词，那么统计完s的频次后，遍历t应该刚好把所有计数清零。如果某个字符变负数，说明t中这个字符比s多，不是异位词。

题目2：字符串中的第一个唯一字符（LeetCode 387）

题目：找出字符串中第一个只出现一次的字符的索引

输入: s = "leetcode" 输出: 0 （'l'只出现一次） 输入: s = "loveleetcode" 输出: 2 （'v'是第一个只出现一次的） 

思路：先统计每个字符的频次，再遍历一遍找第一个频次为1的字符。

publicintfirstUniqChar(String s){// 1. 创建数组统计26个小写字母的频次int[] count =newint[26];// 2. 第一遍遍历：统计每个字符出现的次数for(char c : s.toCharArray()){ count[c -'a']++;// 字符c对应的计数+1}// 3. 第二遍遍历：按原字符串顺序查找第一个出现次数为1的字符for(int i =0; i < s.length(); i++){// 获取当前字符的出现次数if(count[s.charAt(i)-'a']==1){return i;// 找到第一个唯一字符，返回其索引}}// 4. 如果没有找到唯一字符，返回-1return-1;}

为什么要遍历两遍？第一遍统计频次，第二遍按原字符串顺序查找，这样能保证找到的是"第一个"唯一字符。

题目3：赎金信（LeetCode 383）

题目：判断字符串ransomNote能否由字符串magazine中的字符构成

输入: ransomNote = "a", magazine = "b" 输出: false 输入: ransomNote = "aa", magazine = "aab" 输出: true 

思路：统计magazine中每个字符的频次，然后遍历ransomNote，每用一个字符就减1，如果不够用就返回false。

publicbooleancanConstruct(String ransomNote,String magazine){// 1. 创建数组统计magazine中26个小写字母的频次int[] count =newint[26];// 2. 遍历magazine，统计每个字符的可用数量for(char c : magazine.toCharArray()){ count[c -'a']++;// 字符c的可用数量+1}// 3. 遍历ransomNote，检查是否有足够的字符可用for(char c : ransomNote.toCharArray()){ count[c -'a']--;// 使用一个字符c，可用数量-1// 如果某个字符的可用数量变成负数，说明magazine中这个字符不够用if(count[c -'a']<0){returnfalse;}}// 4. 所有字符都够用，可以构成ransomNotereturntrue;}

为什么这样思考？这题本质上是检查magazine是否包含ransomNote所需的所有字符（包括数量），用数组统计频次最直接。

类型2：双指针类

核心思想： 用两个指针从不同位置遍历，避免嵌套循环

什么时候用双指针？

• 回文问题（从两端向中间）
• 反转字符串（交换两端字符）
• 原地修改数组（快慢指针）

模板：对撞指针（判断回文）

publicbooleanisPalindrome(String s){int left =0, right = s.length()-1;while(left < right){if(s.charAt(left)!= s.charAt(right)){returnfalse;// 两端字符不同，不是回文} left++;// 左指针右移 right--;// 右指针左移}returntrue;// 所有字符都对称}

为什么从两端向中间？回文的特点就是对称，从两端比较最直接。时间复杂度O(n)，空间复杂度O(1)。

题目1：验证回文串（LeetCode 125）

题目：判断字符串是否是回文（只考虑字母和数字，忽略大小写）

输入: s = "A man, a plan, a canal: Panama" 输出: true （去掉非字母数字后是"amanaplanacanalpanama"） 

思路：用双指针，遇到非字母数字就跳过，比较时忽略大小写。

publicbooleanisPalindrome(String s){// 1. 初始化双指针：left指向开头，right指向末尾int left =0, right = s.length()-1;// 2. 双指针向中间移动while(left < right){// 3. 左指针跳过所有非字母数字字符（如空格、标点符号）while(left < right &&!Character.isLetterOrDigit(s.charAt(left))){ left++;}// 4. 右指针跳过所有非字母数字字符while(left < right &&!Character.isLetterOrDigit(s.charAt(right))){ right--;}// 5. 比较左右两个字符（转换为小写后比较，忽略大小写）if(Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right))){returnfalse;// 字符不相等，不是回文}// 6. 两个指针向中间移动 left++; right--;}// 7. 所有字符都对称，是回文串returntrue;}

为什么要跳过非字母数字？题目要求只考虑字母和数字，其他字符（空格、标点）都忽略。

题目2：反转字符串（LeetCode 344）

题目：原地反转字符数组

输入: s = ['h','e','l','l','o'] 输出: ['o','l','l','e','h'] 

思路：用双指针从两端向中间交换字符。

publicvoidreverseString(char[] s){// 1. 初始化双指针：left指向开头，right指向末尾int left =0, right = s.length -1;// 2. 双指针向中间移动，交换两端字符while(left < right){// 3. 交换left和right位置的字符char temp = s[left];// 临时保存左边字符 s[left]= s[right];// 右边字符赋值给左边 s[right]= temp;// 左边字符（temp）赋值给右边// 4. 两个指针向中间移动 left++; right--;}// 5. 交换完成，数组已原地反转}

为什么这样思考？反转就是把第一个和最后一个交换，第二个和倒数第二个交换…用双指针最直接。

类型3：滑动窗口类（最重要）

滑动窗口在博主之前的文章里面讲过，可以翻找之前的文章自行观看哦~

核心思想： 维护一个动态窗口，右指针扩大窗口，左指针收缩窗口

什么时候用滑动窗口？

看到这些关键词就想到滑动窗口：

• 最长/最短子串
• 连续子数组
• 包含某些字符的子串

滑动窗口的两种类型

1. 固定窗口： 窗口大小固定，只需要滑动
2. 可变窗口： 窗口大小动态变化，需要收缩

模板：可变窗口（最常用）

publicintslidingWindow(String s){int left =0, maxLen =0;Set<Character> window =newHashSet<>();// 维护窗口内的字符for(int right =0; right < s.length(); right++){char c = s.charAt(right);// 如果窗口内有重复字符，收缩窗口while(window.contains(c)){ window.remove(s.charAt(left));// 移除左边界字符 left++;// 左指针右移}// 加入右边界字符 window.add(c);// 更新最大长度 maxLen =Math.max(maxLen, right - left +1);}return maxLen;}

为什么叫滑动窗口？想象一个窗户在字符串上滑动，窗户里的内容就是当前考虑的子串。右边界不断扩大，左边界根据条件收缩。

题目1：无重复字符的最长子串（LeetCode 3）

题目：找出字符串中不含重复字符的最长子串的长度

输入: s = "abcabcbb" 输出: 3 （"abc"） 输入: s = "pwwkew" 输出: 3 （"wke"） 

思路：用HashSet维护窗口内的字符，遇到重复字符就收缩窗口。

publicintlengthOfLongestSubstring(String s){// 1. 边界条件：空字符串返回0if(s ==null|| s.length()==0)return0;// 2. 初始化变量int left =0;// 窗口左边界int maxLen =0;// 记录最长子串长度Set<Character> window =newHashSet<>();// 用HashSet存储窗口内的字符// 3. 右指针遍历字符串，扩大窗口for(int right =0; right < s.length(); right++){char c = s.charAt(right);// 获取右边界的字符// 4. 如果窗口内已有这个字符（重复了），收缩窗口while(window.contains(c)){ window.remove(s.charAt(left));// 移除左边界字符 left++;// 左指针右移，收缩窗口}// 5. 将右边界字符加入窗口 window.add(c);// 6. 更新最大长度（当前窗口大小 = right - left + 1） maxLen =Math.max(maxLen, right - left +1);}// 7. 返回最长无重复子串的长度return maxLen;}

为什么要用HashSet？HashSet可以O(1)时间判断字符是否存在，比遍历数组快得多。

优化版本：用HashMap记录字符的索引，遇到重复字符可以直接跳到重复位置的下一个。

publicintlengthOfLongestSubstring(String s){if(s ==null|| s.length()==0)return0;int left =0, maxLen =0;Map<Character,Integer> map =newHashMap<>();// 记录字符最后出现的位置for(int right =0; right < s.length(); right++){char c = s.charAt(right);// 如果字符已存在且在窗口内，直接跳到重复位置的下一个if(map.containsKey(c)&& map.get(c)>= left){ left = map.get(c)+1;}// 更新字符位置 map.put(c, right);// 更新最大长度 maxLen =Math.max(maxLen, right - left +1);}return maxLen;}

为什么更快？不需要一个一个移动左指针，直接跳到重复字符的下一个位置。

题目2：找到字符串中所有字母异位词（LeetCode 438）

题目：找出字符串s中所有p的异位词的起始索引

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

思路：固定窗口大小为p的长度，滑动窗口，每次检查窗口内的字符频次是否和p相同。

publicList<Integer>findAnagrams(String s,String p){// 1. 初始化结果列表List<Integer> result =newArrayList<>();// 边界条件：s比p短，不可能包含p的异位词if(s.length()< p.length())return result;// 2. 创建两个数组分别统计p和s窗口内的字符频次int[] pCount =newint[26];// 统计p中每个字符的频次int[] sCount =newint[26];// 统计s窗口内每个字符的频次// 3. 统计p中每个字符的频次for(char c : p.toCharArray()){ pCount[c -'a']++;}// 4. 初始化第一个窗口（长度为p.length()）for(int i =0; i < p.length(); i++){ sCount[s.charAt(i)-'a']++;}// 检查第一个窗口是否是异位词if(Arrays.equals(pCount, sCount)){ result.add(0);// 起始索引0}// 5. 滑动窗口：从索引p.length()开始遍历for(int i = p.length(); i < s.length(); i++){// 窗口右移：加入新字符（右边界） sCount[s.charAt(i)-'a']++;// 窗口右移：移除旧字符（左边界） sCount[s.charAt(i - p.length())-'a']--;// 6. 比较当前窗口的字符频次是否和p相同if(Arrays.equals(pCount, sCount)){// 当前窗口是异位词，记录起始索引 result.add(i - p.length()+1);}}// 7. 返回所有异位词的起始索引return result;}

为什么是固定窗口？异位词长度必须和p相同，所以窗口大小固定。每次滑动只需要更新边界字符的频次，不需要重新统计整个窗口。

题目3：字符串的排列（LeetCode 567）

题目：判断s2是否包含s1的排列（即s1的异位词）

输入: s1 = "ab", s2 = "eidbaooo" 输出: true 解释: s2包含s1的排列之一("ba") 输入: s1 = "ab", s2 = "eidboaoo" 输出: false 

思路：和上一题类似，固定窗口大小为s1的长度，检查窗口内字符频次是否和s1相同。

publicbooleancheckInclusion(String s1,String s2){// 1. 边界条件：s1比s2长，不可能包含s1的排列if(s1.length()> s2.length())returnfalse;// 2. 创建两个数组分别统计s1和s2窗口内的字符频次int[] s1Count =newint[26];// 统计s1中每个字符的频次int[] s2Count =newint[26];// 统计s2窗口内每个字符的频次// 3. 统计s1中每个字符的频次for(char c : s1.toCharArray()){ s1Count[c -'a']++;}// 4. 初始化第一个窗口（长度为s1.length()）for(int i =0; i < s1.length(); i++){ s2Count[s2.charAt(i)-'a']++;}// 检查第一个窗口是否是s1的排列if(Arrays.equals(s1Count, s2Count))returntrue;// 5. 滑动窗口：从索引s1.length()开始遍历for(int i = s1.length(); i < s2.length(); i++){// 窗口右移：加入新字符（右边界） s2Count[s2.charAt(i)-'a']++;// 窗口右移：移除旧字符（左边界） s2Count[s2.charAt(i - s1.length())-'a']--;// 6. 比较当前窗口的字符频次是否和s1相同if(Arrays.equals(s1Count, s2Count)){returntrue;// 找到s1的排列}}// 7. 没有找到s1的排列returnfalse;}

为什么这样思考？s1的排列就是s1的异位词，所以问题转化为：s2中是否存在长度为s1.length()的子串，其字符频次和s1相同。

类型4：动态规划类

核心思想： 把问题分解成子问题，避免重复计算

什么时候用动态规划？

• 最长公共子序列/子串
• 最长回文子串
• 编辑距离

题目1：最长回文子串（LeetCode 5）

题目：找出字符串中最长的回文子串

输入: s = "babad" 输出: "bab" 或 "aba" 输入: s = "cbbd" 输出: "bb" 

思路：回文串的特点是中心对称，从每个可能的中心向两边扩展。

publicStringlongestPalindrome(String s){// 1. 边界条件：空串或单字符直接返回if(s ==null|| s.length()<2)return s;// 2. 初始化变量记录最长回文子串的起始位置和长度int start =0;// 最长回文子串的起始索引int maxLen =0;// 最长回文子串的长度// 3. 遍历每个可能的回文中心for(int i =0; i < s.length(); i++){// 情况1：奇数长度回文（中心是一个字符，如"aba"）int len1 =expandAroundCenter(s, i, i);// 情况2：偶数长度回文（中心是两个字符，如"abba"）int len2 =expandAroundCenter(s, i, i +1);// 4. 取两种情况中较长的回文长度int len =Math.max(len1, len2);// 5. 如果当前回文比之前记录的更长，更新结果if(len > maxLen){ maxLen = len;// 计算回文子串的起始位置// 公式：i - (len - 1) / 2 start = i -(len -1)/2;}}// 6. 返回最长回文子串return s.substring(start, start + maxLen);}// 辅助方法：从中心向两边扩展，返回回文长度privateintexpandAroundCenter(String s,int left,int right){// 当左右字符相等时，继续向两边扩展while(left >=0&& right < s.length()&& s.charAt(left)== s.charAt(right)){ left--;// 左指针左移 right++;// 右指针右移}// 返回回文长度（right - left - 1）// 注意：循环结束时left和right已经越界，所以要-1return right - left -1;}

为什么要考虑奇数和偶数？回文串可能是奇数长度（如"aba"）或偶数长度（如"abba"），中心不同。

题目2：回文子串（LeetCode 647）

题目：统计字符串中有多少个回文子串

输入: s = "abc" 输出: 3 解释: "a", "b", "c" 输入: s = "aaa" 输出: 6 解释: "a", "a", "a", "aa", "aa", "aaa" 

思路：和上一题类似，从每个中心向两边扩展，统计回文子串的数量。

publicintcountSubstrings(String s){// 1. 初始化计数器int count =0;// 2. 遍历每个可能的回文中心for(int i =0; i < s.length(); i++){// 情况1：奇数长度回文（中心是一个字符） count +=expandAroundCenter(s, i, i);// 情况2：偶数长度回文（中心是两个字符） count +=expandAroundCenter(s, i, i +1);}// 3. 返回回文子串总数return count;}// 辅助方法：从中心向两边扩展，返回以该中心为起点的回文子串数量privateintexpandAroundCenter(String s,int left,int right){int count =0;// 记录回文子串数量// 当左右字符相等时，继续向两边扩展while(left >=0&& right < s.length()&& s.charAt(left)== s.charAt(right)){ count++;// 每扩展一次就找到一个新的回文子串 left--;// 左指针左移 right++;// 右指针右移}// 返回以该中心为起点的回文子串数量return count;}

为什么这样思考？每个回文子串都有一个中心，从中心向两边扩展，每扩展一次就找到一个回文子串。

类型5：栈类

核心思想： 利用栈的后进先出特性处理配对问题

什么时候用栈？

• 括号匹配
• 嵌套结构
• 最近的配对元素

题目1：有效的括号（LeetCode 20）

题目：判断括号字符串是否有效（每个左括号都有对应的右括号）

输入: s = "()" 输出: true 输入: s = "()[]{}" 输出: true 输入: s = "(]" 输出: false 

思路：遇到左括号就入栈，遇到右括号就和栈顶匹配。

publicbooleanisValid(String s){// 1. 创建栈用于存储左括号Stack<Character> stack =newStack<>();// 2. 遍历字符串中的每个字符for(char c : s.toCharArray()){// 3. 遇到左括号，入栈if(c =='('|| c =='['|| c =='{'){ stack.push(c);}// 4. 遇到右括号，和栈顶的左括号匹配else{// 如果栈为空，说明没有左括号可以匹配if(stack.isEmpty())returnfalse;// 弹出栈顶的左括号char top = stack.pop();// 检查左右括号是否匹配if(c ==')'&& top !='(')returnfalse;if(c ==']'&& top !='[')returnfalse;if(c =='}'&& top !='{')returnfalse;}}// 5. 最后栈应该为空（所有左括号都已匹配）return stack.isEmpty();}

为什么用栈？括号匹配是典型的"最近配对"问题，最近的左括号应该匹配最近的右括号，这正是栈的后进先出特性。

题目2：简化路径（LeetCode 71）

题目：给定Unix风格的绝对路径，简化为规范路径

输入: path = "/home/" 输出: "/home" 输入: path = "/../" 输出: "/" 输入: path = "/home//foo/" 输出: "/home/foo" 输入: path = "/a/./b/../../c/" 输出: "/c" 

思路：用栈处理路径，遇到"…“就弹出栈顶（返回上级目录），遇到”."或空字符串就跳过，其他情况入栈。

publicStringsimplifyPath(String path){// 1. 创建栈用于存储有效的目录名Stack<String> stack =newStack<>();// 2. 按"/"分割路径，得到各个部分String[] parts = path.split("/");// 3. 遍历每个部分for(String part : parts){if(part.equals("..")){// 4. 遇到".."表示返回上级目录，弹出栈顶（如果栈不为空）if(!stack.isEmpty()){ stack.pop();}}elseif(!part.equals(".")&&!part.isEmpty()){// 5. 遇到普通目录名（不是"."也不是空字符串），入栈// "."表示当前目录，空字符串是多个"/"产生的，都跳过 stack.push(part);}// 6. "."和空字符串都不处理，直接跳过}// 7. 构建结果路径if(stack.isEmpty())return"/";// 栈为空说明在根目录StringBuilder sb =newStringBuilder();// 遍历栈中的所有目录，拼接成路径for(String dir : stack){ sb.append("/").append(dir);}// 8. 返回简化后的路径return sb.toString();}

为什么用栈？路径处理中，"…"表示返回上级目录，这是典型的"撤销"操作，用栈的后进先出特性最合适。

三、解题思维框架

看到题目先问自己3个问题

1. 这是什么类型的问题？

• 字符统计、异位词 → 哈希表
• 子串、子数组 → 滑动窗口
• 回文、反转 → 双指针
• 括号匹配 → 栈
• 最优解 → 动态规划

2. 暴力解法是什么？能优化吗？

• 先想出暴力解法（通常是嵌套循环）
• 再想能否用双指针、滑动窗口、哈希表优化

3. 需要什么数据结构？

• 查找/统计 → HashMap或数组
• 动态窗口 → Set或Map
• 配对问题 → Stack

优化路径

暴力O(n²/n³) ↓ 双指针/滑动窗口 O(n) ↓ 哈希表优化（用空间换时间） ↓ 数组优化（字符集有限时） 

四、常见陷阱

1. 字符串不可变

// 错误：循环里拼接字符串String s ="";for(int i =0; i < n; i++){ s +="a";// 每次都创建新对象，O(n²)}// 正确：用StringBuilderStringBuilder sb =newStringBuilder();for(int i =0; i < n; i++){ sb.append("a");}

2. 字符串比较

// 错误：用==比较字符串if(s1 == s2){}// 比较的是引用// 正确：用equals()if(s1.equals(s2)){}// 比较的是内容

3. 数组越界

// 注意索引范围for(int i =0; i < s.length(); i++){// [0, length)char c = s.charAt(i);}// substring是左闭右开 s.substring(0,3);// [0, 3) 不包含索引3

4. 边界条件

// 完整的边界检查if(s ==null|| s.length()==0)return 默认值;if(s.length()==1)return 特殊处理;

五、刷题路线

入门（10题）- 先把基础打牢

1. 344 反转字符串 - 双指针入门
2. 242 有效的字母异位词 - 哈希表入门
3. 387 字符串中的第一个唯一字符 - 哈希表统计
4. 125 验证回文串 - 双指针+字符判断
5. 28 找出字符串中第一个匹配项的下标 - 字符串匹配
6. 14 最长公共前缀 - 字符串比较
7. 58 最后一个单词的长度 - 字符串遍历
8. 20 有效的括号 - 栈入门
9. 392 判断子序列 - 双指针
10. 383 赎金信 - 哈希表

进阶（15题）- 掌握核心技巧

11. 3 无重复字符的最长子串 - 滑动窗口经典题
12. 5 最长回文子串 - 中心扩展
13. 49 字母异位词分组 - 哈希表分组
14. 151 反转字符串中的单词 - 字符串处理
15. 438 找到字符串中所有字母异位词 - 固定滑动窗口
16. 567 字符串的排列 - 滑动窗口+哈希表
17. 647 回文子串 - 中心扩展变形
18. 205 同构字符串 - 双向映射
19. 290 单词规律 - 哈希表映射
20. 459 重复的子字符串 - KMP或技巧
21. 680 验证回文字符串 II - 双指针+贪心
22. 696 计数二进制子串 - 分组统计
23. 709 转换成小写字母 - 字符处理
24. 771 宝石与石头 - 哈希表查找
25. 819 最常见的单词 - 哈希表统计

六、总结

核心方法速查

// 访问charAt(i),toCharArray(),substring(start, end)// 查找indexOf(),contains()// 判断isEmpty(),equals(),startsWith(),endsWith()// 修改toLowerCase(),toUpperCase(),trim(),replace()// 分割拼接split(),String.join(),StringBuilder.append()

解题三步法

1. 识别题型 - 看关键词选方法
2. 选数据结构 - HashMap/Set/Stack/数组
3. 套模板 - 双指针/滑动窗口/哈希表/栈

记忆口诀

字符统计用哈希 子串问题滑动窗 回文对称双指针 括号配对用栈解 

最重要的：先理解思想，再记模板。每道题都问自己"为什么这样做"，而不是死记硬背。

作者：[识君啊]