渐进式学前端算法

[yanyue404]

专题式学习计划

• 两数之和
• 扁平数组与 tree 相互转换
• Javascript 精度
• diff
• 数据结构：链表、二叉树

1. 两数之和

Leetcode 第一题 https://leetcode.cn/problems/two-sum

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2, 3，7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案
• 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解法 1：

// 暴力双循环
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
const twoSum = function (nums, target) {
  for (let m = 0; m < nums.length; m++) {
    for (let n = 0; n < nums.length; n++) {
      if (nums[m] + nums[n] === target) {
        return [m, n];
      }
    }
  }
};

解法 2：

// 一次循环 + indexOf
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
var twoSum = function(nums, target) {
  var _result
  nums.some(function(item, index) {
    var _index = nums.indexOf(target - item)
    if (_index !== -1 && index !== _index) {
      _result = [index, _index]
      return true
    }
  })
  return _result
}

知识点：indexOf 的时间复杂度？https://juejin.cn/post/7031833133938901022

解法 3：

// 一趟哈希表
// 时间复杂度：O(n)
// 空间复杂度：O(n)
var twoSum = function(nums, target) {
  const map = {}
  for (let i = 0; i < nums.length; i++) {
    const n = nums[i]
    if (target - n in map) {
      return [map[target - n], i]
    } else {
      map[n] = i
    }
  }
}

// 使用 Map
var twoSum = function (nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
};

解法 4：

// 排序 + 双指针
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
var twoSum = function(nums, target) {
  // Array.from 深拷贝一个新的排序后的数组
  let arr = Array.from(nums).sort((a, b) => a - b)
  let i = 0,
    j = arr.length - 1
    while (i < j) {
    if (arr[i] + arr[j] === target) {
      return [nums.indexOf(arr[i]), nums.lastIndexOf(arr[j])]
    } else if (arr[i] + arr[j] > target) {
      j--
    } else {
      i++
    }
  }
}

知识点：如何 copy 一个数组？

数组 item 为基础类型时以下方法为深拷贝：

[...arr]

Array.from(arr)

arr.slice()

arr.concat()

arr.map(v=>v)

arr.filter(v=> true)

Object.assign([], arr)

解法 5：

// 二分法
// 0-500 内的一个数：

target : 365
range: [0, 500]

// 250 [251, 500]
// 375 [251, 374]
// 312 [313, 374]
// 343 [344, 374]
// 359 [360, 374]
// 367 [360, 366]
// 363 [364, 366]
// 365  => 365

// 排序 + 二分法
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
const twoSum = function (nums, target) {
// Array.from 深拷贝一个新的排序后的数组
    const arr = Array.from(nums).sort((a, b) => a - b);
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
      let mid = Math.floor((right + left) / 2);
      if (arr[left] + arr[right] === target) {
        break;
        // 左半部分首尾和已经大于目标值，结果肯定在左半部分
      } else if (arr[left] + arr[mid] > target) {
        right = mid;
        // 右半部分首尾和还是小于目标值，结果肯定在右半部分
      } else if (arr[mid] + arr[right] < target) {
        left = mid;
      } else if (arr[left] + arr[right] < target) {
        left++;
      } else if (arr[left] + arr[right] > target) {
        right--;
      }
    }
    return [nums.indexOf(arr[left]), nums.lastIndexOf(arr[right])];
};