双指针在最大无重复子串及最大回环子串的应用

╰+哭是因爲堅強的太久メ 2024-04-17 19:17 49阅读 0赞

最近在力扣刷了几道题之后，发现双指针的用处还是很大的，可以大大降低代码的时间复杂度，简化代码等等。  
这里讲的指针不是C++里面的指针，说白了就是两个标记，没那么复杂。

# 不含有重复字符的 最长子串 #

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”  
输出: 3  
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/longest-substring-without-repeating-characters][https_leetcode-cn.com_problems_longest-substring-without-repeating-characters]\`\`

### 解题思路： ###

一、**暴力解法**：用多次for循环遍历所有子串，这样的方法不推荐

二、**双指针**  
设置两个指针 start ，end，指针 start 位置不变，end 向后移动，当出现两个字符相同时，再改变 start 和 end 的位置，同时用一个变量 Max 记录最大长度。

public class LongestNoRepeat {
        public static int Longest(String string){
          int Max=0;
          int start=0;
          int end=0;
          while (end<string.length()-1){
              if (string.charAt(end)!=string.charAt(end+1)){
                  end++;
                  Max=Math.max(Max,end-start+1);//动态改变最大长度
              }else {
                  start=end+1;
                  end+=2;
              }
          }
          return Max;
        }
        }

# 最大回环子串 #

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

*  示例 1：

输入: “babad”  
输出: “bab”  
注意: “aba” 也是一个有效答案。

*  示例 2：

输入: “cbbd”  
输出: “bb”

来源：力扣（LeetCode）

public class HuiHuan {
        public  String longestPalindrome(String string){
            int start = 0;
            int end = 0;
            if (string==null||string.length()<=1) return "";
            for (int i=0;i<string.length();i++){
                int len1 = center(string, i, i);//字符个数为奇数的回环子串
                int len2 = center(string, i, i + 1);//字符个数为偶数的回环子串
                int len = Math.max(len1, len2);
                if (len > end - start) {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
    
            }
            return string.substring(start,end+1);
        }
        public int center(String s,int left,int right){
        //以这个范围为中心，向两边拓展，返回符合条件的字符串长度
            int l=left;
            int r=right;
            while (l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
                l--;
                r++;
            }
            return r-l-1;
        }
    
    }

[https_leetcode-cn.com_problems_longest-substring-without-repeating-characters]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters