题解 | 最长无重复子数组

1、解题思路

1. 滑动窗口法：使用双指针（left 和 right）表示当前窗口的左右边界。使用哈希表记录窗口中各元素的最后一次出现的位置。当遇到重复元素时，移动 left 指针到重复元素的下一个位置。更新窗口的最大长度。
2. 复杂度分析：时间复杂度：O(n)，只需要遍历数组一次。空间复杂度：O(n)，哈希表最多存储所有元素的最后一次出现的位置。

2、代码实现

C++

#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        unordered_map<int, int> last_pos;   // 记录元素最后一次出现的位置
        int left = 0;
        int max_len = 0;

        for (int right = 0; right < arr.size(); ++right) {
            if (last_pos.count(arr[right]) && last_pos[arr[right]] >= left) {
                left = last_pos[arr[right]] +
                       1; // 移动左指针到重复元素的下一个位置
            }
            last_pos[arr[right]] = right;   // 更新当前元素的最后位置
            max_len = max(max_len, right - left + 1); // 更新窗口的最大长度
        }

        return max_len;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        // write code here
        Map<Integer, Integer> lastPos = new HashMap<>();
        int left = 0;
        int maxLen = 0;
        
        for (int right = 0; right < arr.length; ++right) {
            if (lastPos.containsKey(arr[right]) && lastPos.get(arr[right]) >= left) {
                left = lastPos.get(arr[right]) + 1; // 移动左指针到重复元素的下一个位置
            }
            lastPos.put(arr[right], right); // 更新当前元素的最后位置
            maxLen = Math.max(maxLen, right - left + 1); // 更新窗口的最大长度
        }
        
        return maxLen;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        last_pos = {}
        left = 0
        max_len = 0
        
        for right, num in enumerate(arr):
            if num in last_pos and last_pos[num] >= left:
                left = last_pos[num] + 1  # 移动左指针到重复元素的下一个位置
            last_pos[num] = right  # 更新当前元素的最后位置
            max_len = max(max_len, right - left + 1)  # 更新窗口的最大长度
        
        return max_len

3、复杂度分析

1. 滑动窗口法 ： 使用双指针动态调整窗口大小，确保窗口内无重复元素。
2. 哈希表辅助 ： 记录每个元素的最后一次出现的位置，快速判断当前窗口是否需要调整。
3. 时间复杂度 ： 只需遍历数组一次，时间复杂度为O(n)。
4. 空间复杂度 ： 哈希表存储的元素数量最多为数组长度，空间复杂度为O(n)。