Algorithm

Problem

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

The solution set must not contain duplicate triplets.

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let len = nums.length;
    let answers = [];
    if (!nums || len < 3) return answers;
    nums.sort((a,b) => a - b); // 将数组进行排序   
    for (let i = 0; i < len -2; i++) {
        if (nums[i] > 0) break; // 排序后的数组，若第一位大于0，则三则之和不可能等于0，不必往下循环
        if (i > 0 && nums[i] == nums[i-1]) continue; // 若标的数重复，则跳过本次循环操作，去重操作
        let L = i + 1; // 左指针，每次循环左指针重置至标的数指针右边一位
        let R = len - 1; // 右指针，每次循环始终从数组最后一位开始
        while (L < R) { // 若左指针大于右指针则结束指针移动
            let sum = nums[i] + nums[L] + nums[R];
            if (sum === 0) { // 匹配成功，左右指针同时移动
                answers.push([nums[i], nums[L] ,nums[R]]);
                L++;
                R--;
                while(L < R && nums[L] === nums[L-1]) L++; // 若左指针移动后数据与之前相等，则继续右移，去重操作
                while(L < R && nums[R] === nums[R+1]) R--; // 若右指针移动后数据与之前相等，则继续左移，去重操作
            } else if (sum > 0) {
                // 若总和大于0，则左移右指针
                R--;
            } else {
                // 若总和小于0，则右移左指针
                L++;
            }
            
        }
        
    }
    return answers;
};

Review

Artical

Understanding Higher-Order Functions in JavaScript

Link

https://blog.bitsrc.io/understanding-higher-order-functions-in-javascript-75461803bad

Review

Functions are the first-class citizens in JavaScript. In JavaScript, functions are special type of objects. We can add properties to functions, assign functions to variables, pass functions as parameters.

A Higher-order function is a function that may receive a function as an argument and can even return a function.

Tips

If you want to chage the value of an array element., you can do it like this:

var merge = function (nums1, m, nums2, n) {
  let i = m - 1
  let j = n - 1
  let k = m + n - 1
  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j])
      nums1[k--] = nums1[i--]
    else
      nums1[k--] = nums2[j--]
  }
  while (j >= 0) {
    nums1[k--] = nums2[j--]
  }
};



Share

Artical

How JavaScript works: inside the V8 engine + 5 tips on how to write optimized code

Link

https://blog.sessionstack.com/how-javascript-works-inside-the-v8-engine-5-tips-on-how-to-write-optimized-code-ac089e62b12e

Summary

How to write optimized JavaScript

1. Order of object properties: always instantiate your object properties in the same order so that hidden classes, and subsequently optimized code, can be shared.

2. Dynamic properties: adding properties to an object after instantiation will force a hidden class change and slow down any methods that were optimized for the previous hidden class. Instead, assign all of an object’s properties in its constructor.

3. Methods: code that executes the same method repeatedly will run faster than code that executes many different methods only once (due to inline caching).

4. Arrays: avoid sparse arrays where keys are not incremental numbers. Sparse arrays which don’t have every element inside them are a hash table. Elements in such arrays are more expensive to access. Also, try to avoid pre-allocating large arrays. It’s better to grow as you go. Finally, don’t delete elements in arrays. It makes the keys sparse.

5. Tagged values: V8 represents objects and numbers with 32 bits. It uses a bit to know if it is an object (flag = 1) or an integer (flag = 0) called SMI (SMall Integer) because of its 31 bits. Then, if a numeric value is bigger than 31 bits, V8 will box the number, turning it into a double and creating a new object to put the number inside. Try to use 31 bit signed numbers whenever possible to avoid the expensive boxing operation into a JS object.