Slide window usage scenario: Generally, you need to traverse the entire array/string to find the subset that meets the criteria.

Use method of sliding window: as shown below. We need two subscripts to mark the window boundary value and determine the size of the window. Because we need to find the maximum value that meets the condition, we need to record the value that meets the requirement every time the window slides until we reach the end, we take the maximum value that meets the condition.

1. Title Description

LeetCode 3. The oldest string without repeating characters

Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3. Example 2:

Input: s = “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1. Example 3:

Input: s = “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wKE”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.

Second, train of thought analysis

Based on the sliding window introduced, let’s apply it to this problem

Boundary values of sliding Windows: x, j

Duplicate characters appear in if

The left edge of the window moves to the right

Compute the maximum value at this point

else

The right border of the window moves to the right

Compute the maximum value at this point

AC code
func lengthOfLongestSubstring(s string) int {
    / / boundary value
	if s == "" {
		return 1
	}
	lenStr := len(s)
	var maxLen int // Maximum length value
	var x, j int  // Slide window boundary value
	for j < lenStr { // Determine whether the sliding window has reached the boundary
		if strings.Contains(s[x:j], string(s[j])) {  // Duplicate characters appear
			x = x + 1  // The left edge of the window moves one unit to the right
			if len(s[x:j+1]) > maxLen {  // Calculate the maximum value
				maxLen = len(s[x : j+1])}}else {
			j++ // The right edge of the window expands
			if len(s[x:j]) > maxLen {
				maxLen = len(s[x:j]) // Calculate the maximum value}}}return maxLen
}
Copy the code
Four,

The principle of sliding Windows is easy to understand, the main difficulty is how to find the optimal value for a given condition. We could use a little more practice

The same series of topics:

  • LeetCode209. Smallest subarray of length

Given an array of n positive integers and a positive integer target.

Find the smallest contiguous subarray [numsl, numSL +1,…, numsr-1, numsr] that satisfies the sum and ≥ target, and return its length. If no subarray exists, return 0.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3] output: 2 description: the subarray [4,3] is the smallest subarray in this condition.

AC code:

func minSubArrayLen(target int, nums []int) int {
	lenNums := len(nums)
	var i, j, ans, minCnt int
	minCnt = lenNums + 1
	for j < lenNums {
		ans = nums[j] + ans
		if ans >= target {
			if j-i+1 < minCnt {
				minCnt = j - i + 1
			}
			ans = 0
			i++
			j = i - 1
		}
		j++
	}
	if minCnt == lenNums+1 {
		minCnt = 0
	}
	return minCnt
}
Copy the code

LeetCode159. The largest string containing at most two distinct characters

Enter: s = “abccbca”

Output: 5

Func ContainsTweChar(s string) int {var charMap map[string]int charMap = make(map[string]int) var lenS = len(s) var i, j int j++ var maxCnt int for j < lenS { charMap[s[i:i+1]] = i if strings.Contains(s[i:j+1], string(s[j])) { charMap[s[j:j+1]] = j } if len(charMap) > 2 { delete(charMap, s[i:i+1]) i++ } j++ if maxCnt < len(s[i:j]) { maxCnt = len(s[i:j]) } } return maxCnt }Copy the code
  • This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign