A Lookup Table is a simple query operation that replaces data structures such as arrays or associative arrays computed at run time. Since extracting values from memory is often much faster than complex calculations, the speed gain is significant.

In human language, input and output are stored in tables so that output can be quickly found from input without complicated calculation.

In algorithms, it is often possible to reduce the time complexity of an operation in an array by turning it into a lookup table:

  • Quickly find the location of a value in the array: iterate through the array, create a Map, value is the key, index is the value, complexity from O(n) to O(1)
  • Quickly find the number of occurrences of a value in the array: iterate through the array, create a Map, value is the key, index is the number of times, complexity from O(n) to O(1)
// The index of each element in the array
function getIndexMap(arr) {
  // Compatible string writing
  const map = {};
  for (let i = 0; i <= arr.length; i++) {
    map[arr[i]] = i;
  }
  return map;
}
// The number of occurrences of each element in the array
function getCountMap(arr) {
  // Compatible string writing
  const map = {};
  for (let i = 0; i <= arr.length; i++) {
    const cur = arr[i];
    map[cur] = map[cur] ? map[cur] + 1 : 1;
  }
  return map;
}
Copy the code

Exercise 1: Intersection of two arrays

Obviously, we’re looking to see if an element has been present in another array, and how many times it has been present.

So here’s the idea:

  • Map the elements and degrees of the array nums1
  • Set the array variable res to represent the final result
  • Iterate over nums2, if there are elements in the Map and the corresponding degree is a positive integer, then push the elements into RES, and subtract the corresponding degree by one, so as to ensure that the element in RES has the minimum number of occurrences
var intersect = function (nums1, nums2) {
  GetCountMap is the function above
  const countMap = getCountMap(nums1);
  const res = [];
  nums2.forEach((item) = > {
    if (countMap[item]) {
      res.push(item);
      countMap[item] = countMap[item] - 1; }});return res;
};
Copy the code

Exercise 2: Find the difference

Strings and arrays are similar:

  • Form a Map of str1 elements and degrees
  • Iterating through str2, return the result if there are no elements in the Map or if the degree is a positive integer, otherwise subtract the degree by one
var findTheDifference = function (s, t) {
  GetCountMap is the function above
  const countMap = getCountMap(s);
  for (let i = 0; i < t.length; i++) {
    const cur = t[i];
    if(! countMap[cur]) {returncur; } countMap[cur]--; }};Copy the code

Of course, since there is only one, there are other ways:

  • The sum of the ASCII values of each character in s and T is the resulting letter
  • S and T are combined, and the bitwise operation gives us the result

But when more than one letter is added, it is better to look up the table:

var findTheDifference = function (s, t) {
  GetCountMap is the function above
  const countMap = getCountMap(s);
  let res = "";
  for (let i = 0; i < t.length; i++) {
    const cur = t[i];
    if(! countMap[cur]) { res += cur; }else{ countMap[cur]--; }}return res;
};
Copy the code

In fact, you can use lookup tables to reduce time complexity as long as the result of a calculation is frequently used

reference

  • Write front-end algorithm advanced guide, I am how two months zero basis brush 200 questions
  • Lookup table overcomplete summary: Resolve lookup problems