Longest non repeating subarray

The main idea of the topic

Given a length of $n$ Array of $arr$ , return $arr$ The length of the longest non repeating element subarray of , No repetition means that all numbers are different .

Subarray is continuous , such as [1,3,5,7,9] The subarrays of are [1,3],[3,5,7] wait , however [1,3,7] It's not a subarray

Data range

$0\le arr.length\le 10^5$

$0<arr[i]\le 10^5$

Examples

 Input ： [2,3,4,5]
 Return value ：4
 explain ：[2,3,4,5] Is the longest subarray      

solution + prove

The topic needs to find the longest non repeating sub array , First of all, make it clear , Subarray must be contiguous
First of all, make it clear ： The largest scale data of this problem can reach $2e5$ Level , If double circulation is adopted , Then it will time out （ The final exam passed because the data was too weak ）
Just a quick introduction ： A normal game machine ,$1s$ You can run $1e7-1e8$ The data of , So if it's a double cycle , Can be achieved in this topic $4e10$ Amount of computation , So it's going to be overtime
Then we need a faster algorithm , To solve this problem
// One idea given by the teacher is dynamic planning , But since I didn't take this idea to solve , So this kind of thinking is not for the time being （ I don't want to be lazy ~╭(╯^╰)╮）

So how do we do that ？

A very simple idea ： If all the numbers , Only once , Then the answer is length

Except in this case , We also need to explore the nature of the topic ： Be careful. ： A longest non repeating subarray , For this subarray , Each element is continuous in position and only appears once , let me put it another way , This array cannot be made larger

Simple proof ： If this array can add an element on the left , Obviously, the new array with new elements is longer than the original array 1, Contradict the original assumption , Adding an element on the right is similar .

therefore , You can get one Important conclusions ： For this subarray of answers , The first element on its left , Or the first element to the right , It must have appeared in the subarray and only once

So what did we think of ？ you 're right , Namely Count

Give a $cnt$ Array , This array is used to record array elements $a[i]$ In a definite interval $[left,right]$ Number of occurrences in

Next , We just need to maintain $[left,right]$ This interval , Ensure that all numbers in the interval appear and only appear once , Specific to the method , That is, we adopt Double pointer , At the left end point $left$ after , Every time you move the right endpoint , Simultaneous counting , If the newly added number leads to the current range $[left,right]$ The number of occurrences of a certain number in is greater than 1, Then we keep moving the left endpoint , Make all numbers in the whole interval appear and only appear once .

Last , It's important to point out that , Although we adopt a double cycle in form , But in essence, the upper limit of this code is $2n$ So there's no overtime

Standard range

Double pointer + Count

/** * * @param arr int Integer one-dimensional array  the array * @param arrLen int arr The length of the array  * @return int integer  * * C Language declaration defines global variables. Please add static, Prevent duplicate definitions  * * C Language declaration defines global variables. Please add static, Prevent duplicate definitions  */
#define N 200005
static int cnt[N];
int maxLength(int* arr, int arrLen ) {
    
    // Special judgement 
    if (arrLen < 2) return arrLen;
    int maxLen = 0;
    // Double pointer , Move the right border 
    int left = 0,right = 0;
    while(right < arrLen)
    {
    
        // Count first 
        cnt[arr[right]]++;
        // The new count causes a number in the interval to appear more than 1
        while(cnt[arr[right]] > 1)
        {
    
            // Start on the left , Delete the numbers until all the numbers in the interval appear and only appear once 
            cnt[arr[left]]--;
            left++;
        }
        // After processing , The right range +1, Ready for the next cycle 
        right++;
        // Update answers 
        maxLen = maxLen > (right - left) ? maxLen : (right - left);
    }
    return maxLen;
}