导航：首页 > 开发技术 >

编程语言中无重复字符最长子串的示例分析

发表于：2024-10-27 作者：千家信息网编辑

千家信息网最后更新 2024年10月27日，小编给大家分享一下编程语言中无重复字符最长子串的示例分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！一、说明给定一个字符

千家信息网最后更新 2024年10月27日编程语言中无重复字符最长子串的示例分析

小编给大家分享一下编程语言中无重复字符最长子串的示例分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

一、说明

给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 `"abcabcbb"` ，没有重复字符的最长子串是 `"abc"` ，那么长度就是3。
给定 `"bbbbb"` ，最长的子串就是 `"b"` ，长度是1。
给定 `"pwwkew"` ，最长子串是 `"wke"` ，长度是3。请注意答案必须是一个子串， `"pwke"` 是 _子序列_ 而不是子串。

二、解决方案参考

1. Swift 语言

class LongestSubstringWithoutRepeatingCharacters {    func lengthOfLongestSubstring(_ s: String) -> Int {        var longest = 0, left = 0, set = Set()        let sChars = Array(s)                for (i, char) in sChars.enumerated() {            if set.contains(char) {                                longest = max(longest, i - left)                                while sChars[left] != char {                    set.remove(sChars[left])                    left += 1                }                left += 1            } else {                set.insert(char)            }        }                return max(longest, sChars.count - left)    }}

2. JavaScript 语言

/** * @param {string} s * @return {number} */var lengthOfLongestSubstring = function(s) {  var hash = {};  var start = 0;  var ans = 0;  for (var i = 0, len = s.length; i < len; i++) {    var item = s[i];    if (!hash[item])      hash[item] = true;    else {      // item 已经在 substring 中存在了      for (; ;) {        if (s[start] === item) {          start++;          break;        }        hash[s[start]] = false;        start++;      }    }    ans = Math.max(ans, i - start + 1);  }  return ans;};

3. Python 语言

class Solution(object):    def _lengthOfLongestSubstring(self, s):        """        :type s: str        :rtype: int        """        d = collections.defaultdict(int)        l = ans = 0        for i, c in enumerate(s):            while l > 0 and d[c] > 0:                d[s[i-l]] -= 1                l -= 1            d[c] += 1            l += 1            ans = max(ans, l)        return ans                    def lengthOfLongestSubstring(self, s):        d = {}        start = 0        ans = 0        for i,c in enumerate(s):            if c in d:                start = max(start, d[c] + 1)            d[c] = i            ans = max(ans, i - start + 1)        return ans

4. Java 语言

// 方式一public class Solution {    public int lengthOfLongestSubstring(String s) {        int n = s.length();        int ans = 0;        for (int i = 0; i < n; i++)            for (int j = i + 1; j <= n; j++)                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);        return ans;    }    public boolean allUnique(String s, int start, int end) {        Set 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;    }}// 方式二public class Solution {    public int lengthOfLongestSubstring(String s) {        int n = s.length();        Set set = new HashSet<>();        int ans = 0, i = 0, j = 0;        while (i < n && j < n) {            // try to extend the range [i, j]            if (!set.contains(s.charAt(j))){                set.add(s.charAt(j++));                ans = Math.max(ans, j - i);            }            else {                set.remove(s.charAt(i++));            }        }        return ans;    }}// 方式三public class Solution {    public int lengthOfLongestSubstring(String s) {        int n = s.length(), ans = 0;        Map map = new HashMap<>(); // current index of character        // try to extend the range [i, j]        for (int j = 0, i = 0; j < n; j++) {            if (map.containsKey(s.charAt(j))) {                i = Math.max(map.get(s.charAt(j)), i);            }            ans = Math.max(ans, j - i + 1);            map.put(s.charAt(j), j + 1);        }        return ans;    }}

5. C++ 语言

#include #include #include #include using namespace std;int lengthOfLongestSubstring1(string s) {    map m;    int maxLen = 0;    int lastRepeatPos = -1;    for(int i=0; i maxLen ){            maxLen = i - lastRepeatPos;        }        m[s[i]] = i;    }    return maxLen;}//don't use int lengthOfLongestSubstring(string s) {    const int MAX_CHARS = 256;    int m[MAX_CHARS];    memset(m, -1, sizeof(m));    int maxLen = 0;    int lastRepeatPos = -1;    for(int i=0; i maxLen ){            maxLen = i - lastRepeatPos;        }        m[s[i]] = i;    }    return maxLen;}int main(int argc, char** argv){    string s = "abcabcbb";    cout << s << " : " << lengthOfLongestSubstring(s) << endl;    s = "bbbbb";    cout << s << " : " << lengthOfLongestSubstring(s) << endl;    s = "bbabcdb";    cout << s << " : " << lengthOfLongestSubstring(s) << endl;    if (argc>1){        s = argv[1];        cout << s << " : " << lengthOfLongestSubstring(s) << endl;    }    return 0;}

6. C 语言

#include #include #include static int lengthOfLongestSubstring(char *s){    int offset[128];    int max_len = 0;    int len = 0;    int index = 0;    memset(offset, 0xff, sizeof(offset));    while (*s != '\0') {        if (offset[*s] == -1) {            len++;        } else {            if (index - offset[*s] > len) {                len++;            } else {         len = index - offset[*s];            }        }        if (len > max_len) {            max_len = len;        }        offset[*s++] = index++;    }    return max_len;}int main(int argc, char **argv){    if (argc != 2) {        fprintf(stderr, "Usage: ./test string");        exit(-1);    }    printf("%d", lengthOfLongestSubstring(argv[1]));    return 0;}

以上是"编程语言中无重复字符最长子串的示例分析"这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！

很赞哦！