思路:

从题中给出的有效信息：

  • 子数组是连续不重复的

判断子集的问题，一般采用dp的思路来解决

方法一：遍历

具体做法：
遍历搜索，遍历出所有连续的字符串，并判断是否符合要求，记录最长字符串的长度，最后返回

import java.util.*;
public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        if (arr.length == 0) {
            return 0;
        }
        int len = arr.length;
        List<Integer> list = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < len; i++) {
            //找出以i位置开头的最长的不重复子串
            for (int j = i; j < len; j++) {
                if (list.contains(arr[j])) { //有重复的就退出循环
                    break;
                } else {
                    list.add(arr[j]); //不重复就一直add
                }
            }
            count = Math.max(count, list.size());
            //当count大于等于剩下的长度时，不再遍历
            if (count >= len - 1 - i) {
                break;
            }
            //清空记录
            list.clear();
        }
        return count;
    }
}

复杂度分析：

  • 时间复杂度：O(n^3) 两次遍历加上集合操作
  • 空间复杂度：O(n) 申请了一个n大小的集合

方法二：动态规划

具体做法：
dp状态定义：以i下标元素为结尾字符的无重复数字的子集合最大长度
遍历到 arr[j] 时，初始化索引 i = j - 1 ，向左遍历搜索第一个满足 s[i] = s[j] 的数字即可

具体过程如下图所示：
图片说明 

import java.util.*;
public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        int res = 0, tmp = 0;
        for(int j = 0; j < arr.length; j++) {
            int i = j - 1;
            while(i >= 0 && arr[i] != arr[j]) i--; // 遍历查找 i
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

复杂度分析：

  • 时间复杂度：O(n^2) n为数组长度，每轮计算 dp[j] 时搜索 i 需要遍历 j 个字符
  • 空间复杂度：O(1) 常数空间复杂度

方法三：哈希+双指针

具体做法：
使用 哈希表统计字符 s[j]s[j] 最后一次出现的索引，每轮更新左边界 i=max(dic[s[j]],i) ，更新结果 res=max(res,j−i)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0;
        for(int j = 0; j < s.length(); j++) {
            if(dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

复杂度分析：

  • 时间复杂度：O(n) 动态规划需遍历计算 dpdp 列表
  • 空间复杂度：O(1) 哈希表使用了常数项的空间（0 — 127）