This is the sixth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

The mapping container provided by Go language is Map, which uses hash internally.

map

A map is an unordered key-value based data structure. In Go, a map is a reference type and must be initialized before it can be used.

The map definition

The map definition syntax in Go language is as follows:

map[KeyType]ValueType

Map variables default to nil and use the make() function to allocate memory. Note: Uninitialized maps can’t be used

make(map[KeyType]ValueType, [cap])

Cap represents the capacity of the map. This parameter is not required, but an appropriate capacity should be specified when the map is initialized. Prevent frequent map expansion

Basic Use of MAP

The data in map comes in pairs. The basic code for using map is as follows:

func main() { scoreMap := make(map[string]int, Println(scoreMap[" scoreMap "]) fmt.println (scoreMap[" scoreMap "]) fmt.printf ("type of a:%T\n", scoreMap) }Copy the code

Output:

100 type of a:map[string]intCopy the code

Map also supports padding elements at declaration time, for example:

Func main() {userInfo := map[string]string{"username": "little prince ", "password": "123456",} FMT.Println(userInfo) //}Copy the code

Determine if a key exists

Value, OK := map[key]

The map of traverse

Go uses for range to traverse a map.

Note: The map in GO is unordered, meaning that the order of insertion and convenience are not necessarily the same.

Delete key-value pairs using the delete() function

Delete a set of key-value pairs from a map using the delete() built-in function, which has the following format:

delete(map, key)

Among them,

  • Map: indicates the map of the key-value pair to be deleted
  • Key: indicates the key of the key-value pair to be deleted

How do I specify a sequential map traversal

We cannot directly traverse the map in order, because the map is unordered, so we can only take out the elements of the map one by one, sort them, and traverse. Go was originally designed to avoid redundant base library operations that can be implemented by themselves.

Map algorithm: Find the largest string that does not contain duplicate characters

Leetcode Original address

1. Violent solution

Time complexity O(n3)(n^3)(n3) Space complexity O(1) will time out. The first layer of the loop takes the ith word as the actual position. The second layer of the loop ends at the JTH bit

2. Slide window — Map

In the violent solution, the second three-layer circular judgment character is too complex, so we can make use of the characteristics of the data structure to make judgment, thus reducing the cycle. I and j are only iterated once

Time complexity O(n), space complexity O(n)

3. Pursue extreme performance

The map’s data structure can be replaced with an array whose index represents the key in the previous example and whose value is similar to the value in the previous example. Because -s consists of letters, numbers, symbols, and Spaces, i.e. ASCii is 127 at most, in this solution, our time and space complexity is still O(n), but we save a lot of time and space by changing map to an array.