算法题（滑动窗口、动态规划）
一、题目
1.无重复字符的最长子串（LC 3）
2.找到字符串中所有字母异位词（LC 438）
3.爬楼梯（LC 70）
4.杨辉三角（LC 118）
5.打家劫舍（LC 198）
二、滑动窗口
1.无重复字符的最长子串（LC 3）
（1）分析
用两个指针表示一个窗口，left和right，保证窗口中永远是不重复的字符串，right向右移动，遇到重复的字符串，就把left向右移动到新字符上一次出现位置的下一个。每次移动right，都要记录此时的字符串长度，最后取最大值。
（2）解答
class Solution { public int lengthOfLongestSubstring(String s) { int length = s.length(); if(length==0){return 0;} int maxLength = 0; Map<Character,Integer> map = new HashMap<>(); int left = 0; for(int right = 0; right<length; right++){ char ch = s.charAt(right); if(map.containsKey(ch)){ left = Math.max(left, map.get(ch)+1); } map.put(ch,right); maxLength = Math.max(maxLength,right-left+1); } return maxLength; } }2.找到字符串中所有字母异位词（LC 438）
（1）分析
遍历字符串s中所有长度等于p的子串，通过统计 26 个小写字母的出现次数判断是否为异位词。若子串与p的字母计数完全一致，则将子串起始下标加入结果列表，最后输出所有的异位词下标。
（2）解答
class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> list = new ArrayList<>(); int slen = s.length(); int plen = p.length(); if (slen < plen) { return list; } for (int i = 0; i < slen - plen + 1; i++) { String str = s.substring(i, i + plen); if (isAnagrams(str, p)) { list.add(i); } } return list; } public boolean isAnagrams(String str, String p) { if(str.length()!=p.length()){return false;} int[] countStr = new int[26]; int[] countP = new int[26]; for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); countStr[ch - 'a']++; } for (int i = 0; i < p.length(); i++) { char ch = p.charAt(i); countP[ch - 'a']++; } return Arrays.equals(countStr,countP); } }三、动态规划
1.爬楼梯（LC 70）
（1）分析
定义dp[i]为爬到第i阶台阶的总方法数。根据每次可爬 1 阶或 2 阶，得到递推式dp[i] = dp[i-1] + dp[i-2]。初始化dp[0] = 1、dp[1] = 1保证递推正常启动。循环计算至dp[n]，最终返回该值即为答案。
（2）解答
class Solution { public int climbStairs(int n) { int[] dp = new int[n+1]; dp[1] = 1; dp[0] = 1; for(int i = 2; i<=n; i++){ dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } }2.杨辉三角（LC 118）
（1）分析
每行第一个和最后一个数字都是 1;
中间每个数字 = 上一行它左上方+正上方 的和;
递推公式：c[i][j] = c[i-1][j-1]+c[i-1][j];
这段代码先固定首尾为 1，再用上层数字计算中间值，逐行构建出完整的杨辉三角。
（2）解答
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> c = new ArrayList<>(numRows); c.add(List.of(1)); for(int i = 1; i<numRows; i++ ){ List<Integer> row = new ArrayList<>(i+1); row.add(1); for(int j = 1; j<i; j++){ row.add(c.get(i-1).get(j-1)+c.get(i-1).get(j)); } row.add(1); c.add(row); } return c; } }3.打家劫舍（LC 198）
（1）分析
边界处理：只有一间房屋时，直接偷这间，返回nums[0]。
dp 数组定义：dp[i]表示前i+1间房屋能偷到的最大金额。
初始化：第一间直接偷，第二间选金额更大的一间。
递推公式：对第i间，要么不偷（取前一间最大值），要么偷（取前两间最大值加当前金额），取两者较大值。
结果：遍历完成后，最后一位dp[nums.length-1]即为全局最大可偷金额。
（2）解答
class Solution { public int rob(int[] nums) { if(nums.length==1){ return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] =Math.max(nums[0],nums[1]); for(int i = 2; i<nums.length; i++){ dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]); } return dp[nums.length-1]; } }