Force buckle the first problem: the sum of two numbers.

Title description:

A function that takes two arguments, an array and a target number, and finds two numbers in the array where the sum of the two elements equals the target number (there must be a valid answer).

A, violence,

Go through two layers to find the answer.

function twoSum(nums: number[], target: number) :number[] {
    let result = []
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if(nums[i] + nums[j] === target) { result.push(i); result.push(j); }}}return result;
};
Copy the code

I could write it that way, but it’s too violent, 132ms, notice the problem, there’s only one valid answer for each test case, and if you find it at the beginning, then the rest of the iteration is meaningless. Optimize for this condition.

function twoSum(nums: number[], target: number) :number[] {
    let result = []
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                result.push(i);
                result.push(j);
                returnresult; }}}};Copy the code

Change one line of code, now run 88ms, is that optimization?

Time complexity O(N2)O(N^2)O(N2), space complexity O(1)O(1)O(1).

Second, the HashMap

Think: Which step takes time?

Answer: The process of finding the difference.

For each element, finding a value equal to target-nums [I] in the other array elements is the most time-consuming step. So what’s the solution?

Data structures exist to make certain actions in certain scenarios more profitable. So what data structure is appropriate for this scenario?

Let’s start with hash tables. This is a type of data structure that accesses the location of the data stored in memory directly based on the key, that is, a function f(key) calculates the location of the value in the array to speed up the lookup. This function f() is called a hash function, and the array of records is called a hash table.

🌰 If you want to find a certain wechat friend (key), the first step is to open the wechat address book (set up a hash table), the second step is to click the letter on the right to find the friend’s first letter (set up a hash function from the name to the first letter), and the third step is to find the friend in the list of initials.

If you have multiple surnames that start with the same letter, what do you do? This is called hash conflict. If the hash function evaluates multiple keys to the same hash value, you can use the zipper method to solve this problem. The so-called zipper method is that the array of records does not store values directly, but stores the head of a linked list, which is appended to the end of the list in each subsequent addition, thus resolving conflicts. The whole process is to calculate the hash value of the key through the hash function, find the corresponding subscript of the array according to the hash value, and append to the linked list in the subscript.

There are other optimizations that can be made, such as a list lookup that requires traversal, and if the list stores too many elements, it’s not efficient. So there’s a zipper variant, where instead of using a linked list, you use a tree, like a red-black tree, for example? Another solution is open addressing. The whole idea is that when the hash address conflicts (pit occupied), the hash address 1 is used to generate a hash address 2. If 2 is still occupied, another hash address 1 is used to generate another hash address until there is a pit. The problem with open addressing, however, is that each hash address may be associated with the next and the next, so be careful about deleting, usually soft.

In this way, objects in JS look very much like hash tables. It is true that the object of JS is a data structure with a Hash structure, but not a Hash table. It is a string-value mapping, whereas a Hash table is a value-value mapping. So ES6 provides a more complete Map data structure to use hash tables in JS.

What is 🌰 array? Arrays in serious languages are probably linearly stored data structures, not only logically but physically. The elements are arranged one by one in memory, so you need to specify the size when defining them so that you don’t create too much space and waste it. Arrays can be stored randomly because all the elements in an array are of the same data type, so they take up the same physical space and can be read by subscripting the lower offset.

Remember the array of JS, is it an array? Or is it just an array?

V8 source code as proof:

JSArray is a JavaScript array object that can be stored in one of two modes:

  • Fast:FixedArrayThe type andlength <= element.length()
  • Slow: hash table with numbers as keys

We don’t know what FixedArray is, but we do know that JSObject is a JavaScript Object in this naming style, which is an array inheriting an object. So is it possible to think that an array is actually:

const arr = [1.2.3];
/ / for translation
const arr = {
    '0': 1.'1': 2.'2': 3,}Copy the code

So that’s why arr[‘0’] can also do element access?

Off topic, put the problem solution:

function twoSum(nums: number[], target: number) :number[] {
    let map = new Map(a);for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i];
        } else {
            map.set(nums[i], i)
        }
    }
};
Copy the code

Yeah, good. It runs 86ms. WTF!!!!!! A little faster than brute force?

Analyze the complexity: the time complexity is O(N)O(N)O(N), and the space complexity is also O(N)O(N)O(N) O(N). Space for time, but that’s not much of an improvement.

Three, the original moment

function twoSum(nums: number[], target: number) :number[] {
    for (let i = 0; i < nums.length; ++i) {
        const result = target - nums[i];
        const order = nums.indexOf(result, i+1);
        if(order ! = = -1) {
            return [i, order]
        }
    }
};
Copy the code

122ms, not too bad.

function twoSum(nums: number[], target: number) :number[] {
    let dic = {}
    for (let i = 0; i < nums.length; ++i) {
        if (target - nums[i] in dic) {
            return [dic[target-nums[i]], i]
        }
        dic[nums[i]] = i
    }
};
Copy the code

80ms, so-so.

function twoSum(nums: number[], target: number) :number[] {
    for (let i = 0; i < nums.length; ++i) {
        if(nums.lastIndexOf(target - nums[i]) ! == i && nums.lastIndexOf(target - nums[i]) >=0) {
            return [i, nums.lastIndexOf(target - nums[i])]
        }
    }
};
Copy the code

484ms, it blew up.

All right, it’s bedtime. There are more ways to write it. You know, sort things out first, filter things out first, blah, blah. Just be happy.