首页 > 试题广场 > 找到字符串的最长无重复字符子串
[编程题]找到字符串的最长无重复字符子串
  • 热度指数:50435 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个数组arr,返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。
示例1

输入

[2,3,4,5]

输出

4
示例2

输入

[2,2,3,4,3]

输出

3

备注:
用LinkedList的removeFirst()调整list的长度并记录
例如:{2,3,4,3}遇到重复元素,remove之后是{4,3}
import java.util.*;

public class Solution {
    public int maxLength (int[] arr) {
        LinkedList<Integer> list = new LinkedList<>();
        int p=0, ans=0;
        for(int i=0;i<arr.length;i++){
            if(list.contains(arr[i])){
                int j=list.indexOf(arr[i]);
                while (j-->=0){
                    list.removeFirst();
                }
            }
            list.add(arr[i]);
            ans=Math.max(ans,list.size());
        }
        return ans;
    }
}



发表于 2020-09-14 14:57:48 回复(5)

这个题的双指针用起来简单而优雅。可以用哈希集或哈希表来去重:

哈希集的实现稍微慢一点,因为哈希集没有计数功能,所以碰到重复元素后去重时需要左指针一步步前进:

public int lengthOfLongestSubstring(String s) {
        char[] a = s.toCharArray();
		int n = a.length;
        if(n < 2) return n;
        int res = 0;
        HashSet set = new HashSet();
        int i = 0, j = 0;
        while (j < n) {
            if (!set.contains(a[j])) {
                set.add(a[j]);
                j++;
            } else {
                set.remove(a[i]);
                i++;
            }
            res = Math.max(res, set.size());
        }
        return res;
	}
用哈希表实现更快,因为哈希表可以用键来存储数组元素,用值来存储数组元素的位置,这样碰到重复元素后左指针的移动可以一步到位,不需要一步步走。
public int lengthOfLongestSubstring(String s) {
        char[] a = s.toCharArray();
        int n = a.length;
        if(n < 2) return n;
        int res = 0;
        HashMap<Character,Integer> map= new HashMap<>();
        int i = 0, j = 0;
        while (j < n) {
            if (!map.containsKey(a[j])) {
                map.put(a[j], j);
            } else {
                i = Math.max(i, map.get(a[j])+1);
                map.put(a[j], j);
            }
            res = Math.max(res, j - i + 1);
            j++;
        }
        return res;
    }

发表于 2020-09-09 17:17:57 回复(6)
//之前创建了set 显示超时,改用位子标记 部分查找 不增加变量的存储
int maxLength(vector<int>& arr) {
       int res(0);
    int counter(0);
    for(auto i = arr.begin(); i != arr.end(); i++)
    {
        counter = 0;
        for(auto t = i; t != arr.end(); t++)
        {
            if(find(i,t,*t) != t)
            {
                res = max(res, counter);
                break;
            }
            else
            {
                counter++;
            }
        }
        res = max(res, counter);
    }
    return res;
    }
发表于 2020-12-21 10:21:48 回复(0)
PYTHON solution:
class Solution:
    def maxLength(self , arr ):
        # write code here
        res=[]
        length=0
        for i in arr:
            if i not in res:
                res+=[i]
            else:
                res = res[res.index(i)+1:] + [i]
            if length<len(res): length= len(res)
        return length


发表于 2020-11-29 23:29:03 回复(4)
int maxLength(vector<int>& arr) {
        // write code here
        int n=arr.size();
        int l=0,r=0;
        set<int>s;
        int res=0;
        while(r<n){
            if(!s.count(arr[r])){
                s.insert(arr[r]);
                r++;
            }
            else{
                s.erase(arr[l]);
                l++;
            }
            res=res>s.size()?res:s.size();
        }
        return res;

发表于 2020-09-14 16:19:30 回复(2)
滑动窗口
import java.util.*;

public class Solution {
    public int maxLength (int[] arr) {
        int len = arr.length;
        int left = 0;
        int right = 0;
        int res = 0;
        boolean valid = false;     // 表示窗口是否满足无重复元素
        HashMap<Integer, Integer> map = new HashMap<>();     // 窗口中各个数字出现的情况,key:数字,value:该数出现的次数
        while (right < len) {
            int add = arr[right];
            right++;
            map.put(add, map.getOrDefault(add, 0) + 1);
            if (map.get(add) == 1) {    // 判断该数是否只出现一次
                valid = true;
            } else {
                valid = false;
            }

            // 缩小窗口
            while (!valid) {
                int remove = arr[left];
                map.put(remove, map.get(remove) - 1);
                if (map.get(remove) == 1){    // 如果该数出现的次数减为1则窗口满足条件
                    valid = true;
                }
                left++;
            }
            // 更新结果
            res = Math.max(res, right - left);
        }
        return res;
    }
}


发表于 2021-02-22 23:17:30 回复(0)
/**
 * 
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 */
int maxLength(int* arr, int arrLen ) {
    int n[100000] = {0};
    int left = 0;
    int right = 0;
    int res = 0;
    while (right < arrLen) {
        if (n[arr[right]] > 0) {
            n[arr[left]] = 0;
            left++;
        } else {
            n[arr[right]] = 1;
            res = res > right - left + 1 ? res : right - left + 1;
            right++;
        }
    }
    return res;
}

发表于 2021-02-21 15:36:32 回复(0)
class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        std::map<int, int> tmp;
        int result = 0;
        for (int i = 0; i < arr.size();) {
            auto iter = tmp.find(arr[i]);
            if (iter != tmp.end()) {
                i = iter->second + 1;
                if (tmp.size() > result) {
                    result = tmp.size();
                }
                tmp.clear();
            } else {
                tmp.insert(std::make_pair(arr[i], i));
                ++i;
            }
        }
        return result;
    }
};
面试小米的时候,面试官出的题目。
朴素的方法,就是拿个临时的空间去记录串,向后遍历arr,查看值是否在串中出现。
出现了就比较最大值和临时空间里的数据谁大,然后清空临时空间,下标跑回去;没有出现就把值扔到临时空间里。

我考虑优化的点,就是不想让下标往回跑太多,跑太多实际上是无意义的,正好跑到重复值的后一个下标就好。所以这里很蛋疼的用了个map来记录值和下标。

注:STL可能会影响性能,主要是写的省事,习惯用STL了,又没有什么打比赛的需求。(逃
发表于 2021-01-15 20:24:16 回复(2)
class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        
        map<int, int> num_index;  //检查是否越界了的map工具
        map<int, int>::iterator iter; //迭代器
        int before = 0;
        int after = 1;
        int max_len = 1;
        int arr_len = arr.size();
        num_index[arr[0]] = 0;
        int temp_len = 1;
        int next_before = 0;
        
        //下面开始在线的动态测量过程
        for (after = 1; after < arr_len; after++)
        {
            if (before > arr_len - max_len) //设置一个判断是否可以直接终止的情况,为了节省时间
                break;
            iter = num_index.find(arr[after]); //判断是否在当前的map中
            if (iter == num_index.end())  //当前集合没有该键值对
            {
                num_index[arr[after]] = after;  //匹配该值和所在的位置索引值
                temp_len++;
            }
            else  //当前集合存在该键值对,重复了
            {
                next_before = iter->second;
                if (temp_len > max_len) //更新最大长度值
                {
                    max_len = temp_len;
                }
                temp_len = after - next_before;
                if (next_before - before < after - next_before) //map删除前面的,保留后面的,最后再加上一个after
                {
                    for (int i = before; i <= next_before; i++) //一个一个删除前面的部分
                    {
                        num_index.erase(arr[i]);
                    }
                    num_index[arr[after]] = after;
                }
                else //直接清空map,从next_before往后一个一个加进来,加到after
                {
                    num_index.clear();
                    for (int i = next_before + 1; i <= after; i++)
                    {
                        num_index[arr[i]] = i;
                    }
                }
                before = next_before + 1;
            }
        }
        if (temp_len > max_len)
            max_len = temp_len;
        return max_len;
    }
};

发表于 2020-12-16 21:10:44 回复(0)
import java.util.*;
public class Solution {
    public int maxLength (int[] arr) {
        if(arr.length<2) return arr.length;
        // write code here
        Stack<Integer> stack = new Stack<>();
        int res_lat = 0;
        for(int i=0;i<arr.length;i++){
            int pre =stack.search(arr[i]);
            int lat =stack.size()-stack.search(arr[i])+1;
            if(pre==-1){
                stack.push(arr[i]);
                res_lat=res_lat>stack.size()?res_lat:stack.size();
            }else{
                 res_lat=res_lat>stack.size()?res_lat:stack.size();
                for(int j=0;j<lat;j++){
                    stack.remove(0);
                }
                stack.push(arr[i]);
            }
        }
        return res_lat;
    }
}

发表于 2020-09-23 16:01:34 回复(0)
import java.util.*;

public class Solution {
    /**
     * 有点类似滑动窗口,从左到右遍历,遇到重复的,找到重复的索引,左指针++
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        int start = 0;
        int end = -1;
        int maxLen = 0;
        Map<Integer,Integer> map  = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i]) && map.get(arr[i]) >= start) {
                start = map.get(arr[i]) + 1;
            }
            map.put(arr[i],i);
            end++;
            if (end-start+1>maxLen){
                maxLen = end-start+1;
            }
        }
        return maxLen;
    }
}

发表于 2020-09-19 15:11:00 回复(0)
可以使用 c 语言的 hashtable 进行解题。hashtable的初始值是 0 , 所以我们在坐标计算时 让i多加 1.
思路是这样的,由于hashtable可以轻松的查找到 对应key的值的大小,我们把目标数组的成员作为hashtable的key存入 hashtable,并将 数组成员在数组的位置 +1 作为key值存入。当遇到hashtable中已存在的 数组中的数,则令 start 角标 位 这个数 之前 在 hashtable 中的key值。用 i+1 - start 来判断不重复子串的长度。流程如下图:








代码段:
/**
 * 
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 */

int maxLength(int* arr, int arrLen ) {
    // write code here
    int hashTable[100000] = {0};
    int maxlen = 1;   
    int start = 0;
    for(int i = 0; i < arrLen; i ++)
{
      
    if(hashTable[arr[i]] > start)
    {
        
      

        //printf("%d\n",len);
        start = hashTable[arr[i]];
    }
        hashTable[arr[i]] = i+1;
         if(maxlen < i - start +1)
         {
             maxlen = i-start+1; 
                               //printf("max %d\n",maxlen)                         
         }
      
             
            
    

}
 
    
    return maxlen;
}

发表于 2020-09-22 10:52:11 回复(0)
class Solution {
public:
    int maxLength(vector<int>& arr) {
        // write code here
        int m[40000] = {0};//用map更好
        unsigned int ans = 1, l = 0;//l记录重复位置
        arr.push_back(arr[arr.size() - 1]);//尾部添加一个重复数据使其必然触发(3)条件
        for(int i = 0; i < arr.size(); ++i){
            if(m[arr[i]]){// (3)
                if(ans < i - l)
                     ans = i - l;
                if(m[arr[i]] > l)//只需在重复时记录下重复数据的位置
                    l = m[arr[i]];
            }
            m[arr[i]] = i + 1; 
        }
        return ans;
    }
};

发表于 2020-09-17 11:36:42 回复(3)
class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        int l = 0, r = 0, ans = 0;;
        set<int> s;
        while (r < arr.size()) {
            if (!s.count(arr[r])) {
                s.insert(arr[r++]);
            } else{
                s.erase(arr[l++]);
            }
            ans = ans > s.size() ? ans : s.size();
        }
        return ans;
    }
};

发表于 2020-09-15 22:05:59 回复(1)

import java.util.*;
import java.lang.*;

//从0开始遍历,将遍历的结果放入hashmap,当发生hash冲突时,将遍历的位置向前移动
//到相同数字的地方,并且把当前map的size和maxSize比较

public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
      //定义一个hashmap,key为第i位数字,value为i
        Map<Integer,Integer> map=new LinkedHashMap<>();
        int maxSize=0;
        int i=0;
        while(i<arr.length){
   //发生hash冲突说明前面已经有相同的数了,那个将i移动到前面那个数的位置
            if(map.containsKey(arr[i])){
                maxSize=map.size()<maxSize?maxSize:map.size();
                i=map.get(arr[i]);
                map.clear();
            }else{
                map.put(arr[i],i);
            }
            i++;
        }
        maxSize=map.size()<maxSize?maxSize:map.size();
        return maxSize;
    }
}

发表于 2020-09-13 21:11:24 回复(1)
# 滑动窗口
class Solution:
    def maxLength(self , arr ):
        # write code here
        ans, j = 0, 0
        dst = {}
        for i, num in enumerate(arr):
            if num in dst:
                j = max(j, dst[num])
            ans = max(ans, i+1-j)
            dst[num] = i+1
        return ans



# 堆栈
class Solution:
    def maxLength(self , arr ):
        # write code here
        stack = []
        ans = 0
        for num in arr:
            while num in stack:
                stack.pop(0)
            stack.append(num)
            ans = max(ans, len(stack))
        return ans

编辑于 2021-03-01 19:56:32 回复(0)
Python双指针,利用in语法代替map
class Solution:
    def maxLength(self , arr ):
        if len(arr) <= 1:
            return len(arr)
        # write code here
        fast,slow = 1,0
        maxLen = 0
        while fast < len(arr):
            if arr[fast] not in arr[slow:fast]:
                fast += 1
            else:
                slow += 1
            maxLen = max(maxLen,fast-slow)
        return maxLen

发表于 2021-02-28 23:48:27 回复(0)
代码采用双指针思路,c语言正常运行,python运行超时?
/** C语言版本
 * 
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 */
int maxLength(int* arr, int arrLen ) {
        int first = 0;
        int end = 1;
        int max_len = 0;
        int prt = first;
        if(arrLen <= 1)
        {
            return arrLen;
        }

        while(end < arrLen)
        {
            for(prt = first;prt<end;prt++)
            {
                if(arr[end] == arr[prt])
                {
                    if(end - first > max_len)
                    {
                        max_len = end - first;
                    }
                    first = prt + 1;
                    break;     
                }
            }
            end += 1;            
        }

        if(end - first  > max_len)
        {
             max_len = end - first;           
        }

        return max_len;
    // write code here
}
#  python版本,运行超时
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self , arr ):
        if len(arr) <= 1:
            return len(arr)
        first = 0
        end = 1
        max_len = 0
        while end < len(arr):
            prt = first
            for temp in arr[first:end]:
                if arr[end] == temp:
                    if end - first > max_len:
                        max_len = end - first
                    first = prt + 1
                    break
                prt += 1
            end += 1
        if end - first  > max_len:
            max_len = end - first
        return max_len
            # write code here
C语言版本只用了64ms ,python版本虽然慢但为啥效率差别这么大,无法通过?


发表于 2021-02-23 10:19:13 回复(0)
class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        set<int> unique;
        int l=0,r=0;
       // int i=0;
        int res=0;
        while(r<arr.size())
        {
            if(!unique.count(arr[r]))  
            {
                unique.insert(arr[r]);
                r++;
            }
            else
            {
                unique.erase(arr[l]); //这里注意一下,当上面的if首次判断不通过时,这下面的else很可能会被多次执行
                l++;                    //直到将与当前arr[r]相同的值删除为止
               
            }
             res=res>unique.size()?res:unique.size();
        }
            return res;
        
    }
};

编辑于 2021-02-11 15:39:51 回复(0)
哪里错了?
class Solution:
    def maxLength(self , arr ):
        # write code here
        sets = set(arr)
        return len(sets)

编辑于 2021-02-05 18:41:10 回复(1)