Classical Sliding Window problem.
This is a classical problem where sliding window technique is used.\n\nSliding window is a technique in which we are interested in looking at a window of consec
This is a classical problem where sliding window technique is used.\n\nSliding window is a technique in which we are interested in looking at a window of consecutive elements, for example:\nIf we have an array arr[]={ 1, 2, 3, 4, 5 }, then the sliding window between 2nd and 4th element would be: { 2, 3, 4 }.\n\nAnother important interview problem where sliding window is used is:\nhttps://leetcode.com/problems/longest-substring-without-repeating-characters/\n\nThese two problems are absolutely similar except for one there are characters and in one there are numbers.\n\nApproach:\n1. In this problem, we have to make sure that our sliding window contains unique numbers only.\n2. To Achieve this, we use a HashSet<> and a variable sum to store sum of unique elements of a particular sliding window and max to store the maximum sum of the sliding window having unique elements.\n3. Let i and j be starting and ending index of the sliding window.\n4. While j is less than length(nums), traverse the array, now there are only two possibilities:\n\t* \tIf set does not contain(nums[j]), it means that it is a new element to be added to the sliding window. Add this element to sliding window by adding it to sum and hash set and increase j by 1. Also, keep updating max.\n\t* \tElse if the set contains(nums[j]), then simply start removing the elements from the start of the sliding window until the set does not contain(nums[j]). Every time you remove an element from the start of sliding window, decrease the sum by nums[i], and decrement i by 1.\n5. Return max. \n\nSolution: JAVA\n```\nclass Solution {\n    public int maximumUniqueSubarray(int[] nums) {\n       \n\t   //Length of array\n        int n=nums.length;\n\t\t\n\t\t//Sum of unique elements in a particular window\n        int sum=0;\n        int max=0;\n\t\t\n\t\t//Starting index of the sliding window\n        int i=0;\n        int j=0;\n        Set<Integer> set=new HashSet<Integer>();\n        while(j<n){\n            if(!set.contains(nums[j])){\n                set.add(nums[j]);\n                sum+=nums[j];\n                j++;\n                if(max<sum){\n                    max=sum;\n                }\n            }\n            else{\n                set.remove(nums[i]);\n                sum-=nums[i];\n                i++;\n            }\n        }\n        return max;\n    }\n}\n```\nTime Complexity: O(n), Since the array is traversed only once.\nSpace Complexity: O(n), Since in the worst case all the numbers can be unique.\n\nThanks! Keep coding, keep learning!!!
[]