龙空技术网

力扣-无重复字符串的最长子串的各种解法

四名 101

前言:

此时咱们对“最长子串动态规划”大约比较关心,咱们都想要了解一些“最长子串动态规划”的相关文章。那么小编也在网摘上汇集了一些有关“最长子串动态规划””的相关知识,希望各位老铁们能喜欢,姐妹们快快来学习一下吧!

昨天面试一个候选人一个算法题:无重复字符的最长子串

吭哧吭哧半天一行代码没写出来啊,后来我尝试提示他,先从暴力解法入手应该怎么想?还是没思路,哎呀妈想让你面试通过是真的难。

#来点儿干货#​无重复字符的最长子串是一个常见的字符串处理问题,可以通过滑动窗口的方法来解决。滑动窗口是一种数组/字符串问题处理方法,通过维护一个窗口,能够在O(N)的时间复杂度内解决问题。

滑动窗口思路初始化:创建一个整数变量 maxLen 用来保存最长子串的长度,初始化为0。创建两个指针 left 和 right,分别表示窗口的左右边界,初始化都为0。滑动窗口:创建一个哈希集合 HashSet 来存储窗口中的字符,确保字符的唯一性。移动右指针 right 来扩展窗口,每次循环向 HashSet 中添加一个新字符。检查重复:如果新添加的字符在 HashSet 中已存在,说明窗口中有重复字符,此时需要移动左指针 left,并从 HashSet 中移除对应的字符,直到移除了重复的字符。更新最大长度:在每次右指针移动后,更新 maxLen 的值,使其保持为当前最长无重复字符子串的长度。循环结束条件:当右指针 right 移动到字符串的末尾时,结束循环。滑动窗口Java 解法

下面是解决这个问题的 Java 代码实现:

import java.util.HashSet;public class Solution {    public int lengthOfLongestSubstring(String s) {        HashSet<Character> set = new HashSet<>();        int maxLen = 0;        int left = 0;        for (int right = 0; right < s.length(); right++) {            char c = s.charAt(right);            // 如果字符已存在于HashSet中,移动左指针并从HashSet中移除字符            while (set.contains(c)) {                set.remove(s.charAt(left));                left++;            }            // 添加当前字符到HashSet中            set.add(c);            // 更新最大子串长度            maxLen = Math.max(maxLen, right - left + 1);        }        return maxLen;    }    public static void main(String[] args) {        Solution solution = new Solution();        String s = "abcabcbb";        System.out.println(solution.lengthOfLongestSubstring(s)); // 输出应为 3    }}

该代码实现了无重复字符最长子串的查找,并且时间复杂度是O(N),其中N是字符串的长度。每个字符最多被访问两次(一次是右指针移动,一次是左指针移动)。

上述是效率最高的解法,可能确实不容易想到,但是除此之外还有很多其他解法啊;咱不至于啥也想不到啊。

解法 1:暴力法

这是最直观的方法,枚举所有的子串,然后检查每个子串是否含有重复的字符。这种方法的时间复杂度是O(n^3),空间复杂度是O(min(n, m)),其中n是字符串的长度,m是字符集的大小。

public class Solution {    public int lengthOfLongestSubstring(String s) {        int n = s.length();        int maxLen = 0;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j <= n; j++) {                if (allUnique(s, i, j)) {                    maxLen = Math.max(maxLen, j - i);                }            }        }        return maxLen;    }    public boolean allUnique(String s, int start, int end) {        Set<Character> set = new HashSet<>();        for (int i = start; i < end; i++) {            Character ch = s.charAt(i);            if (set.contains(ch)) return false;            set.add(ch);        }        return true;    }}
解法 2:优化的暴力法

可以对暴力法进行一定的优化,例如,当我们找到一个重复的字符时,不需要从上一个起始位置的下一个字符开始重新检查,而是直接跳过重复的字符。

解法 3:动态规划 + 哈希表

使用动态规划的思想,我们可以记录以第i个字符结尾的最长无重复字符的子串长度,并利用哈希表来存储字符最后一次出现的位置。

import java.util.HashMap;public class Solution {    public int lengthOfLongestSubstring(String s) {        HashMap<Character, Integer> map = new HashMap<>();        int maxLen = 0;        int left = 0;        for (int right = 0; right < s.length(); right++) {            char c = s.charAt(right);            if (map.containsKey(c)) {                left = Math.max(map.get(c) + 1, left);            }            map.put(c, right);            maxLen = Math.max(maxLen, right - left + 1);        }        return maxLen;    }}

在这个解法中,我们利用哈希表来降低时间复杂度,使得每个字符只需要被访问一次,从而将时间复杂度降低到O(n)。

解法 4:使用数组作为简易哈希表

如果字符集较小,比如只有ASCII字符,我们可以使用一个整数数组代替哈希表来存储字符的索引,从而进一步提高效率。

public class Solution {    public int lengthOfLongestSubstring(String s) {        int[] index = new int[128]; // 假设字符集为ASCII        int maxLen = 0;        for (int right = 0, left = 0; right < s.length(); right++) {            char c = s.charAt(right);            left = Math.max(index[c], left);            maxLen = Math.max(maxLen, right - left + 1);            index[c] = right + 1; // 更新字符的索引位置        }        return maxLen;    }}

在这个解法中,数组 index 用来存储每个字符最后一次出现的位置的下一个位置,这样可以直接跳过重复的字符。

所有这些方法中,滑动窗口和动态规划+哈希表是最常用且效率最高的,尤其是在处理大型数据或者字符集较大的情况下。

标签: #最长子串动态规划