算法剖析-经典150（双指针、滑动窗口）

双指针

1.验证回文串

1.答案

1. package com.sunxiansheng.classic150.g1;
3. /**
4. * Description: 125. 验证回文串
5. *
6. * @Author sun
7. * @Create 2024/12/19 15:03
8. * @Version 1.0
9. */
10. public class t125 {
12.     public static boolean isPalindrome(String s) {
13.         // 直接双指针
14.         int left = 0;
15.         int right = s.length() - 1;
16.         while (left < right) {
17.             // 获取左右字符
18.             char leftChar = s.charAt(left);
19.             char rightChar = s.charAt(right);
20.             // 如果不是数字和字母，就直接下一位
21.             if (!Character.isDigit(leftChar) && !Character.isLetter(leftChar)) {
22.                 left++;
23.                 continue;
24.             }
25.             if (!Character.isDigit(rightChar) && !Character.isLetter(rightChar)) {
26.                 right--;
27.                 continue;
28.             }
29.             // 大写转换小写
30.             leftChar = Character.isUpperCase(leftChar) ? Character.toLowerCase(leftChar) : leftChar;
31.             rightChar = Character.isUpperCase(rightChar) ? Character.toLowerCase(rightChar) : rightChar;
32.             // 到这里左右都是数字字母字符了，可以直接比较
33.             if (leftChar != rightChar) {
34.                 return false;
35.             }
36.             left++;
37.             right--;
38.         }
39.         return true;
40.     }
42.     public static void main(String[] args) {
43.         System.out.println("isPalindrome("A man, a plan, a canal: Panama") = " + isPalindrome("A man, a plan, a canal: Panama"));
44.     }
45. }

复制代码

2.思路

就是直接利用双指针，如果不是数字和字母，就直接下一位，大写转换小写，然后比较即可
2.判断子序列

1.动态规划解法

1. package com.sunxiansheng.classic150.g1;
3. /**
4. * Description: 392. 判断子序列
5. *
6. * @Author sun
7. * @Create 2024/12/21 09:36
8. * @Version 1.0
9. */
10. public class t392 {
12.     public boolean isSubsequence(String s, String t) {
13.         // dp[i][j]:以i-1，j-1为结尾的最长公共子序列的长度
14.         // 状态转移公式：相同时 dp[i][j] = dp[i - 1][j - 1] + 1 不同时 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
15.         // 初始化
16.         int m = s.length();
17.         int n = t.length();
18.         int[][] dp = new int[m + 1][n + 1];
19.         int max = 0;
20.         // 填充dp数组
21.         for (int i = 1; i <= m; i++) {
22.             for (int j = 1; j <= n; j++) {
23.                 if (s.charAt(i - 1) == t.charAt(j - 1)) {
24.                     dp[i][j] = dp[i - 1][j - 1] + 1;
25.                 } else {
26.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
27.                 }
28.                 max = Math.max(max, dp[i][j]);
29.             }
30.         }
31.         return max ==  s.length();
32.     }
33. }

复制代码

2.双指针

1. package com.sunxiansheng.classic150.g1;
3. /**
4. * Description: 392. 判断子序列
5. *
6. * @Author sun
7. * @Create 2024/12/21 09:36
8. * @Version 1.0
9. */
10. public class t392 {
12.     public static boolean isSubsequence(String s, String t) {
13.         // 双指针
14.         int left = 0;
15.         for (int right = 0; right < t.length(); right++) {
16.             // 如果左数组已经遍历完了就提前退出
17.             if (left >= s.length()) {
18.                 break;
19.             }
20.             // 当右指针遇到了左指针指向的元素，左指针++
21.             if (t.charAt(right) == s.charAt(left)) {
22.                 left++;
23.             }
24.         }
25.         return left >= s.length();
26.     }
27. }

复制代码

3.两数之和 II - 输入有序数组

1.答案

1. package com.sunxiansheng.classic150.g1;
3. /**
4. * Description: 167. 两数之和 II - 输入有序数组
5. *
6. * @Author sun
7. * @Create 2024/12/21 10:08
8. * @Version 1.0
9. */
10. public class t167 {
12.     public int[] twoSum(int[] numbers, int target) {
13.         // 两个指针从两边往中间移动
14.         int left = 0;
15.         int right = numbers.length - 1;
16.         while (left < right) {
17.             // 求和
18.             int sum = numbers[left] + numbers[right];
19.             // 如果大于target，就右指针移动，小于target就左指针移动
20.             if (sum > target) {
21.                 right--;
22.             } else if (sum < target) {
23.                 left++;
24.             } else {
25.                 return new int[]{left + 1, right + 1};
26.             }
27.         }
28.         return null;
29.     }
30. }

复制代码

2.思路

这里用的是贪心双指针，就是两个指针从双方往中间移动，和如果大于target，就右指针移动，小于target就左指针移动
4.盛最多水的容器

1.答案

1. package com.sunxiansheng.classic150.g1;
3. /**
4. * Description: 11. 盛最多水的容器
5. *
6. * @Author sun
7. * @Create 2024/12/21 10:42
8. * @Version 1.0
9. */
10. public class t11 {
12.     public static int maxArea(int[] height) {
13.         int max = 0;
14.         int left = 0, right = height.length - 1;
15.         while (left < right) {
16.             // 求水量
17.             int water = Math.min(height[left], height[right]) * (right - left);
18.             // 更新最大值
19.             max = Math.max(max, water);
20.             // 哪边低移动哪边的指针
21.             if (height[left] < height[right]) {
22.                 left++;
23.             } else {
24.                 right--;
25.             }
26.         }
27.         return max;
28.     }
29. }

复制代码

2.思路

利用贪心双指针解决
5.三数之和

1.答案

1. package com.sunxiansheng.classic150.g1;
3. import java.util.ArrayList;
4. import java.util.Arrays;
5. import java.util.List;
7. /**
8. * Description: 15. 三数之和
9. *
10. * @Author sun
11. * @Create 2024/12/21 10:50
12. * @Version 1.0
13. */
14. public class t15 {
16.     public static List<List<Integer>> threeSum(int[] nums) {
17.         // 使用遍历+贪心双指针来解决
18.         List<List<Integer>> res = new ArrayList<>();
19.         // 如果数组长度小于3，直接返回空结果
20.         if (nums == null || nums.length < 3) {
21.             return res;
22.         }
23.         // 首先排序
24.         Arrays.sort(nums);
25.         // 遍历
26.         for (int i = 0; i < nums.length - 2; i++) {
27.             // 关键点：当前的元素跟前一个元素是相同的情况下不必考虑
28.             if (i > 0 && nums[i] == nums[i - 1]) {
29.                 continue;
30.             }
31.             // 贪心双指针
32.             int left = i + 1;
33.             int right = nums.length - 1;
34.             while (left < right) {
35.                 // 求结果
36.                 int sum = nums[left] + nums[right] + nums[i];
37.                 // 根据结果来贪心的调整状态
38.                 if (sum > 0) {
39.                     right--;
40.                 } else if (sum < 0) {
41.                     left++;
42.                 } else {
43.                     res.add(Arrays.asList(nums[i], nums[left], nums[right]));
44.                     // 关键点：当左右指针指向的下一个元素跟当前元素是相同的也不用考虑
45.                     while (left < right && nums[left] == nums[left + 1]) {
46.                         left++;
47.                     }
48.                     while (left < right && nums[right] == nums[right - 1]) {
49.                         right--;
50.                     }
51.                     left++;
52.                     right--;
53.                 }
54.             }
55.         }
56.         return res;
57.     }
58. }

复制代码

2.思路

利用遍历+贪心双指针来解决，注意两个关键点一个是在遍历时，遇到重复元素就跳过，另一个是在左右指针移动时，遇到重复元素也跳过
滑动窗口

1.长度最小的子数组

1.答案

1. package com.sunxiansheng.classic150.g1;
3. /**
4. * Description: 209. 长度最小的子数组
5. *
6. * @Author sun
7. * @Create 2024/12/21 11:20
8. * @Version 1.0
9. */
10. public class t209 {
12.     public static int minSubArrayLen(int target, int[] nums) {
13.         // 滑动窗口定义：窗口内的元素要小于target
14.         int left = 0;
15.         int res = Integer.MAX_VALUE;
16.         int sum = 0;
17.         for (int right = 0; right < nums.length; right++) {
18.             // 加入窗口
19.             sum += nums[right];
20.             // 只要窗口内的元素是大于target的，就进行处理
21.             while (sum >= target) {
22.                 // 计算结果
23.                 res = Math.min(res, right - left + 1);
24.                 // 滑动窗口
25.                 sum -= nums[left++];
26.             }
27.         }
28.         return res == Integer.MAX_VALUE ? 0 : res;
29.     }
30. }

复制代码

2.思路

先辈行滑动窗口的界说窗口内的元素要小于target，那么只要窗口内的元素是大于target的，就进行处理，就可以盘算结果了
2.无重复字符的最长子串

1.答案

1. package com.sunxiansheng.classic150.g1;
3. import java.util.HashSet;
4. import java.util.Set;
6. /**
7. * Description: 3. 无重复字符的最长子串
8. *
9. * @Author sun
10. * @Create 2024/12/21 11:28
11. * @Version 1.0
12. */
13. public class t3 {
15.     public static int lengthOfLongestSubstring(String s) {
16.         // 滑动窗口定义：窗口内的元素不能重复
17.         int left = 0;
18.         int res = 0;
19.         Set<Character> set = new HashSet<>();
20.         for (int right = 0; right < s.length(); right++) {
21.             // 获取set的长度
22.             int before = set.size();
23.             // 加入窗口
24.             set.add(s.charAt(right));
25.             res = Math.max(res, set.size());
26.             // 当窗口内的元素重复时
27.             if (set.size() == before) {
28.                 while (s.charAt(left) != s.charAt(right)) {
29.                     // 滑动窗口
30.                     set.remove(s.charAt(left));
31.                     left++;
32.                 }
33.                 // 到这里就说明当前left指向了那个重复元素，继续滑动窗口，不过不需要移动set
34.                 left++;
35.             }
36.         }
37.         return res;
38.     }
39. }

复制代码

2.思路

这里面比较复杂一点，十分考察对滑动窗口算法的明白，加入窗口前先要获取一下加入set之前的长度，如果加入窗口后长度不变，那么就一定是元素重复了，需要滑动窗口直到不重复。盘算结果则是在加入窗口的时候
3.最小覆盖子串

1.答案

1. package com.sunxiansheng.classic150.g1;
3. import java.util.HashMap;
4. import java.util.Map;
6. /**
7. * Description: 76. 最小覆盖子串
8. *
9. * @Author sun
10. * @Create 2024/12/21 14:19
11. * @Version 1.0
12. */
13. public class t76 {
15.     public static String minWindow(String s, String t) {
16.         // 滑动窗口定义：窗口内元素不能全部包含t的所有元素
17.         // 使用map来记录t的词频
18.         Map<Character, Integer> tMap = new HashMap<>();
19.         for (int i = 0; i < t.length(); i++) {
20.             tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
21.         }
22.         // 所有的字符数（当满足条件的字符数为n时，表明该子串就是覆盖子串了）
23.         int n = t.length();
24.         // 满足条件的字符数
25.         int satisfy = 0;
26.         // s的词频
27.         Map<Character, Integer> sMap = new HashMap<>();
28.         // 最小覆盖子串的长度
29.         int minSonLength = Integer.MAX_VALUE;
30.         // 最小覆盖子串
31.         String minSon = "";
32.         int left = 0;
33.         for (int right = 0; right < s.length(); right++) {
34.             // 获取到目标字符
35.             char c = s.charAt(right);
36.             // 只考虑是t的元素的情况
37.             if (tMap.containsKey(c)) {
38.                 // 加入窗口
39.                 sMap.put(c, sMap.getOrDefault(c, 0) + 1);
40.                 // 如果目标字符的出现次数是小于t中的频率，就可以增加满足条件的字符数
41.                 if (sMap.get(c) <= tMap.get(c)) {
42.                     satisfy++;
43.                 }
44.             }
45.             // 只要目前是覆盖子串，就需要滑动窗口
46.             while (satisfy == n) {
47.                 // 更新最小覆盖子串
48.                 if ((right - left + 1) < minSonLength) {
49.                     minSon = s.substring(left, right + 1);
50.                     minSonLength = right - left + 1;
51.                 }
52.                 // 滑动窗口
53.                 // 当是t的元素时
54.                 if (tMap.containsKey(s.charAt(left))) {
55.                     // 更新词频和满足的字符数
56.                     sMap.put(s.charAt(left), sMap.get(s.charAt(left)) - 1);
57.                     // 只有当窗口中的元素减少后，确实比t中的词频少了，才会减少满足的字符数
58.                     if (sMap.get(s.charAt(left)) < tMap.get(s.charAt(left))) {
59.                         satisfy--;
60.                     }
61.                 }
62.                 // 不是t的元素就直接滑动即可
63.                 left++;
64.             }
65.         }
66.         return minSon;
67.     }
69.     public static void main(String[] args) {
70.         minWindow("ADOBECODEBANC", "ABC");
71.     }
72. }

复制代码

2.思路

焦点就是利用Map来记录两个字符串的词频，然后当满意条件的字符数量为t的个数时就是覆盖子串
​

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。