手写算法

四数之和

18. 四数之和

思路

1. 其实跟三数之和的算法是相同的，都是利用双指针，前后移动计算和，只不过四数之和比三数之和多一个 for 循环

2. 计算 n 数之和的时候，如果题目说明数字不能重复，那么我们第一个应该想到的就是排序。这样去重的时候就很方便，只需要对比当前元素和前一个元素的值，相等的话，就跳过

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  let result = [];
  const len = nums.length;
  if (len < 4) return result;
  nums.sort((a, b) => a - b);

  for (let i = 0; i < len - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < len - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let l = j + 1,
        r = len - 1;
      while (l < r) {
        const sum = nums[i] + nums[j] + nums[l] + nums[r];
        if (sum < target) {
          l++;
          continue;
        }
        if (sum > target) {
          r--;
          continue;
        }
        result.push([nums[i], nums[j], nums[l], nums[r]]);
        while (l < r && nums[l] === nums[++l]);
        while (l < r && nums[r] === nums[--r]);
      }
    }
  }
  return result;
};

搜索旋转排序数组

33. 搜索旋转排序数组

思考

1. 分析题意，用 O(logn)完成此题，第一个想到的就是二分查找法

2. 找到一个 mid，将数组分成两块，[left, mid] [mid + 1, right]

3. 接下来就是需要判断 target 在哪个部分

• 如果[left, mid]是个有序数组，且 target 满足[nums[left], nums[mid]],那么 target 在它们之间，否则就在[mid + 1, right]中

• 同样如果[mid + 1, right] 是个有序数组，且 target 满足[nums[mid + 1], nums[right]]，那么 target 在它们之间，否则在[left, mid - 1]中

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  const len = nums.length;
  let left = 0,
    right = len - 1;

  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] === target) return mid;

    // [left, mid] 是升序数组
    if (nums[left] <= nums[mid]) {
      // [left, mid)
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // (mid + 1, right] 是升序数组
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
};

手写题: 生成 Fibonacci 数

86. 生成 Fibonacci 数

用 hash 表

/**
 * @param {number} n - non-negative integer
 * @return {number}
 */
function fib(n) {
  let cache = {};
  function memo(n) {
    if (n < 2) return n;
    cache[n] ??= memo(n - 1) + memo(n - 2);
    return cache[n];
  }
  return memo(n);
}

function fib(n, map = new Map()) {
  if (n < 2) return n;

  if (map.has(n)) {
    return map.get(n);
  }

  const sum = fib(n - 1) + fib(n - 2);
  map.set(n, sum);
  return sum;
}

console.log(fib(10));
console.log(fib(40));
console.log(fib(1000));