preface

Recently BRUSH up on an algorithm problem in leetCode, which involves Sliding windowing algorithm, so write an article to summarize a little

Algorithm problem introduction

Example: Input: “abcabcbb” Output: 3 Explanation: Since the subcharacter without repeating characters is’ ABC ‘, the length is 3

Solution 1: Violent solution

Public class Solution {// Time complexity high O(n3) public int lengthOfLongestSubstring(String s) {int n = s.length(); int ans = 0; // Get the substring with two tags, one representing the beginning and one representing the end of the substringfor (int i = 0; i < n; i++)
            for(int j = i + 1; j <= n; J++) // ans records the maximum length when there are no repeated letters in the substringif (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        returnans; Public Boolean allUnique(String s, int start, int end) {//HashSet implements the Set interface, which does not allow duplicate elements in a Set. Set<Character>set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true; }}Copy the code

Analysis of the

Time complexity: O(N3).

Solution 2: sliding window algorithm

By using HashSet as a sliding window, checking whether a character already exists in an existing subcharacter is just O(1). Sliding Windows are often treated as an abstract concept for array/string problems. A window represents a set of data/string elements, defined by a leading and ending index.

Public class Solution {public int lengthOfLongestSubstring(String s) {int n = s.length(); Set<Character>set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while(I < n &&j < n) {// Try to extend the range [I, j]if(! The set contains (s.c harAt (j))) {/ / ifsetSet. Add (s.char (j++)); set. Add (s.char (j++)); ans = Math.max(ans, j - i); // Record the maximum subcharacter length that exists}else{/ / ifsetIf set.remove(s.charat (i++)) does not exist in the window, move the left side of the window one space to the right. }}returnans; }}Copy the code

Analysis of the

Time complexity: O(2n). In the worst case, each character will be accessed twice

Solution 3: optimized sliding window algorithm

The sliding window algorithm above requires at most 2n steps, but this can be optimized to take only N steps. We can use HashMap to define the mapping between characters and indexes, and then, when we find repeated characters in a substring, we can just skip over the iterated characters.

Public class Solution {// Time complexity o(n) public int lengthOfLongestSubstring(String s) {int n = s.length(), ans = 0; Map<Character, Integer> Map = new hashMap <>(); // current index of character // try to extend the range [i, j]for(int j = 0, i = 0; j < n; J ++) {//j is responsible for traversing to the right, and I adjusts for repeated charactersifI = math.max (map.get(s.char (j)), I); (map.get(s.char (j)); } ans = math.max (ans, j-i + 1); Map. put(s.charat (j), j+1); }returnans; }}Copy the code

Analysis of the

Time complexity: O(n)

Summary of sliding window algorithm

  • The sliding window algorithm can be used to solve the problem of array/string child elements
  • The sliding window algorithm can transform the nested FOR loop problem into a single loop problem, reducing the time complexity