As you already know, a set represents a distinct set of elements (elements that do not repeat). In a dictionary, pairs of keys and values are stored, where key names are used to query for specific elements. A dictionary is similar to a collection in that a collection stores elements in the form of values, while a dictionary stores elements in the form of keys, values. Dictionaries are also called mappings, symbol tables, or associative arrays.

In ES6, the Map class was added to serve as a data structure for dictionaries.

Several methods of Map

set(key: any, value: any)

Use to set the keys and values of the dictionary

const m = new Map(a); m.set('a'.'aaa');
m.set('b'.'bbb');
m.set('c'.'ccc');
console.log(m); // Map(3) {"a" => "aaa", "b" => "bbb", "c" => "ccc"}
Copy the code

has(key: any)

Used to determine whether the dictionary contains an passed key

const m = new Map(a); m.set('a'.'aaa');
m.set('b'.'bbb');
m.set('c'.'ccc');

console.log(m.has('c')); // true
console.log(m.has('d')); // false
Copy the code

get(key: any)

Gets the value of a key in the dictionary

const m = new Map(a); m.set('a'.'aaa');
m.set('b'.'bbb');
m.set('c'.'ccc');

console.log(m.get('c')); // ccc
console.log(m.has('d')); // undefined
Copy the code

size

Gets the length of the dictionary

const m = new Map(a); m.set('a'.'aaa');
m.set('b'.'bbb');
m.set('c'.'ccc');

console.log(m.size); / / 3
Copy the code

delete(key: any)

Use to delete a dictionary value

const m = new Map(a); m.set('a'.'aaa');
m.set('b'.'bbb');
m.set('c'.'ccc');
m.delete('c');
console.log(m); //Map(2) {"a" => "aaa", "b" => "bbb"}
Copy the code

clear()

Used to empty a dictionary

const m = new Map(a); m.set('a'.'aaa');
m.set('b'.'bbb');
m.set('c'.'ccc');
m.clear();
console.log(m); //Map(0) {}
Copy the code

Dictionary algorithms

349. Intersection of two arrays

Code ideas:

We can use a dictionary to store the items in one of these arrays. We then iterate through another array, select the values in it, and push them into the RES array.

/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}* /
var intersection = function(nums1, nums2) {
    const m = new Map(a);const result = [];
    nums1.forEach(item= > {
        m.set(item, true);
    })
    nums2.forEach(item= > {
        if(m.has(item)) { result.push(item); m.delete(item); }})return result
};
Copy the code

20. Valid parentheses

Code ideas:

If we look at a valid parenthesis, we can see that as long as it’s a valid parenthesis, then the last open parenthesis that touches the close parenthesis must correspond to the close parenthesis. And if it’s nested parentheses. So the first open bracket must match the last close bracket (in, out). This is where you can think of a data structure called a stack. That is, when you hit the open bracket, you push the stack, and when you hit the close bracket, you go out of the stack. If the open and close brackets don’t match, return false.

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function(s) {
    const arr = s.split(' ');
    if (arr.length % 2! = =0) {return false;
    }

    const m = new Map(a); m.set('('.') ');
    m.set('['.'] ');
    m.set('{'.'} ');

    const stack = [];
    for(let i = 0 ; i < arr.length ; i++) {
        const item = arr[i];
        if (m.has(item)){
            stack.push(item);
        }
        if (m.get(stack[stack.length - 1]) === item) {
            stack.pop();
        } else if(! m.has(item)){return false; }}return stack.length === 0;
};

Copy the code

1. Sum of two numbers

Code ideas:

This is a very common algorithm problem, and we can use something like a dating agency, where you have to find a target. Then, in the process of searching, if there is an object you want, return, if not, you have to register the data (store the dictionary).

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
    const m = new Map(a);for (let i = 0; i < nums.length; i++ ) {
        if(m.has(nums[i])){
            return [i, m.get(nums[i])];
        } else{ m.set(target - nums[i], i); }}};Copy the code

3. The oldest string with no duplicate characters

Code ideas:

Similar to the substring problem, the first thing we need to think about is using double Pointers to maintain a sliding window.

  1. Keep moving the right pointer, first to determine whether there is a right pointer across the item in the dictionary, if not, it will be stored in the dictionary, if there is, it has encountered repeated characters. Here we can start moving the left pointer, moving the left pointer to the position of the dictionary record pointer +1.
  2. Keep recording the length of r minus L plus 1. (Using the math.max function).
/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function(s) {
    let l = 0;
    let max = 0;
    let m = new Map(a);for (let r = 0; r < s.length; r++){const c = s[r];
        if (m.has(c) && m.get(c) >= l){// The important thing here is to ensure that the dictionary values are located within the window
            l = m.get(c) + 1;
        }
        m.set(c, r);
        max = Math.max(max, r - l + 1);

    }
    return max;
};

Copy the code

76. Minimum override substring

Code idea: use double pointer to control a sliding window

  1. First convert the target value into a dictionary, the sum of key subcharacters and value subcharacters.
  2. Keep moving the right pointer. At the same time, check whether the value of the right pointer exists in the dictionary. If so, set the dictionary value to -1. When the dictionary value is 0, it is proved that one type of character already satisfies the requirement. When all types of characters meet the requirements. We start narrowing the substring (moving the left pointer) until the left pointer character is a dictionary value, at which point the substring no longer satisfies the criteria. Let’s start moving the right pointer until we’re done.

Code implementation:

/ * * *@param {string} s
 * @param {string} t
 * @return {string}* /
var minWindow = function(s, t) {
    let l = 0;
    let r = 0;
    let res = ' ';
    let m = new Map(a);for (let v of t) {
        m.set(v, m.has(v)? m.get(v) + 1: 1);
    }
    let needType = m.size;

    while (r < s.length){
        const c1 = s[r];
        if (m.has(c1)) {
            m.set(c1, m.get(c1) - 1);
            if (m.get(c1) === 0) {
                needType -=1;
            }

            while(needType === 0) {// Find a substring that matches the condition
                const c2 = s[l];
                const newRes = s.substring(l, r + 1);
                if(! res || newRes.length < res.length) {res = newRes};// Keep refreshing the smallest string
                if (m.has(c2)) {
                    m.set(c2, m.get(c2) + 1);
                    if (m.get(c2) === 1){needType +=1};
                }
                l++; // Shrink the window to reduce the length of the substring
            }
        }
        r++;
    }
    return res;
};

Copy the code