Recently I have been looking at data structures and algorithms, trying to sum up my debut ~

  • Try Map optimization when nesting through the same array.

Because the time complexity of nested traversal is O(n^2), which is a bit large, we can think of replacing space with time. During traversal, we can record the traversal elements and their corresponding subscripts. The commonly used recording method is Map.

The advantage of Map is that the time complexity of the search is O(1), and the Map is created for the already traversed elements to reduce the search complexity.

  • Almost any summation problem can be converted to a difference problem, which makes it a lot easier.

Exercise: Sum of two numbers

Without an algorithmic foundation, the first idea is nested traversal.

  • Enumerates all combinations of different subscripts
  • Let’s see if the sum is target
var twoSum = function (nums, target) {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (nums[i] + nums[j] === target) {
        return[i, j]; }}}};Copy the code

Obviously space O(1), time O(n^2).

Think about the principles and optimize!

Nested traversal thinking of Map, space for time, summation turns to difference.

  • A Map is used to record the numbers that have been traversed and their corresponding index values during the traversal of a number array.
  • Each time a new number is iterated, see if the difference between target and that number is in the map
  • Directly return the answer in, otherwise continue to store back
const twoSum = function (nums, target) {
  // Use objects to simulate a map, storing iterated elements and indexes
  const map = {};
  const len = nums.length;
  // go through the number group
  for (let i = 0; i < len; i++) {
    const cur = nums[i];
    const diff = target - cur;
    // see if the difference is in the map
    if (diff in map) {
      // Return the answer in seconds
      return [map[diff], i];
    }
    // If not, store it and continue iteratingmap[cur] = i; }};Copy the code

So space is O(n) and time is O(n)~~

Check out the official video

reference

  • The front-end algorithm and data structure of xiuyan