题解 | #NC41-最长无重复子数组#

/**
 * 
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return int整型
 */
/***************************************************************
* 如何校验数字是否相同？如果以此循环遍历，那效率就太低了，可以尝试用新数组ret[100000]实现哈希
* 定义i为左窗口，初值为0，j为右窗口，初值也为0，右窗口向右移动
* 例如输入[2,2,3,4,3]，ret[100000]新数组元素初值都为0，用数组标记每个数字出现的次数
* ret[arr[i]]==2时说明数字之前出现过，是重复的，那么用ret[arr[i]]--实现出窗口
* 一直将左窗口移动到重复数字右侧，j-i+1即为当前长度，如果比更新前大，则更新窗口长度，否则不更新
************************************************************************/
int maxLength(int* arr, int arrLen ) {
    // write code here
    if(arrLen == 0 || arrLen ==1)
        return arrLen;
    
    int ret[100000] = {0};
    int retLen = 0;
    
    for(int i=0, j=0; j < arrLen; j++)
    {
        ret[arr[j]]++;
        while(ret[arr[j]] > 1)//重复字符，将窗口移动到重复字符右侧
        {
            ret[arr[i]]--;
            i++;
        }
        if(j-i+1 > retLen)
            retLen = j-i+1;
    }
    return retLen;
}