Double pointer in the same direction, double pointer, sliding window 3, 594, |27, 26, 80, 83, 82, 611, 187, 643, 674, 209, 438, 567, 424, 76, 30

3. Longest substring without repeating characters

Given a string , Please find out that there are no duplicate characters in it Longest substrings The length of .

Example 1:
Input : “abcabcbb”
Output : 3
explain : Because the longest substring without repeating characters is “abc”, So its length is 3.
Example 2:
Input : “bbbbb”
Output : 1
explain : Because the longest substring without repeating characters is “b”, So its length is 1.
Example 3:
Input : “pwwkew”
Output : 3
explain : Because the longest substring without repeating characters is “wke”, So its length is 3.
Please note that , Your answer must be Substring The length of ,“pwke” Is a subsequence , Not substring .

Answer key ：
1） The sliding window Traversal string , A character that does not appear map, Slide to the right , And reset max. Characters encountered , Slide the left side to this position .

sloution：

  class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        if (s.length() == 0)
            return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0, j = 0; i < s.length(); ++i) {
    
            if (map.containsKey(s.charAt(i))) {
    
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - j + 1);
        }
        return max;
    }
}

594. The longest harmonious subsequence

A harmonious array means that the difference between the maximum and minimum values of elements in an array is just 1. Now? , Given an array of integers , You need to find the length of the longest harmonious subsequence among all possible subsequences .

Example 1:
Input : [1,3,2,2,5,2,3,7]
Output : 5
reason : The longest harmonious array is ：[3,2,2,2,3].

Answer key ：
1）hash mapping See hash statistics set
2） Double pointer after sorting Similar to sliding window
sloution：

class Solution {
    
    public int findLHS(int[] nums) {
    
        Arrays.sort(nums);
        int begin = 0,res = 0;
        for(int end = 0;end < nums.length;end++){
    
            while(nums[end] - nums[begin] > 1)
                 begin++;
            if(nums[end] - nums[begin] == 1)
              res = Math.max(res,end - begin + 1);
        }
        return res;
    }
}