参考知识点：

• JS 知识点 - 数字

1. 携程：大数相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1：

输入：num1 = "9856356712356", num2 = "61356137653"

输出："604747979200385261940468"

示例 2：

输入：num1 = "9856356712356", num2 = "0"

输出："0"

思路：

模拟竖式乘法，从个位数开始，逐位相乘，然后将结果相加。

这个过程要模拟大数乘一位数、大数加法。

function multiply(a, b) {
  if (a.length < b.length) {
    return multiply(b, a);
  }
  let ans = "0";
  for (let i = b.length - 1; i >= 0; i--) {
    const db = b[i];
    ans = add(ans, mul(a, db) + "0".repeat(b.length - 1 - i));
  }
  const index = ans.split("").findIndex(x => x !== "0");
  return ans.slice(index);

  function mul(a, d) {
    const ans = [];
    let carry = 0;
    for (let i = a.length - 1; i >= 0; i--) {
      const da = a[i];
      const res = Number(da) * Number(d) + carry;
      ans.push(res % 10);
      carry = Math.floor(res / 10);
    }
    if (carry > 0) {
      ans.push(carry);
    }
    return ans.reverse().join("");
  }

  function add(a, b) {
    let i = a.length - 1, j = b.length - 1;
    const ans = [];
    let carry = 0;
    while (i >= 0 || j >= 0) {
      const da = a[i--] || 0, db = b[j--] || 0, res = Number(da) + Number(db) + carry;
      ans.push(res % 10);
      carry = Math.floor(res / 10);
    }
    if (carry > 0) {
      ans.push(carry);
    }
    return ans.reverse().join("");
  }
}

用数组存储结果的每一位数，将两个数的每一位数做一位数的乘法，然后将结果累加到对应的位置上。

最后将数组做进位处理，并转换为字符串，注意去除前导 0。

function multiply(a, b) {
  const m = a.length, n = b.length;
  const ans = new Array(m + n).fill(0);
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      ans[i + j + 1] += Number(a[i]) * Number(b[j]);
    }
  }
  for (let i = ans.length - 1; i >= 0; i--) {
    if (ans[i] >= 10) {
      const temp = ans[i];
      ans[i] %= 10;
      ans[i - 1] += Math.floor(temp / 10);
    }
  }
  const index = ans.findIndex(x => x !== 0);
  return ans.slice(index).join("");
}

2. 58：斐波那契数列前 n 项和

给定一个正整数 n，求斐波那契数列的前 n 项和。

示例 1：

输入：n = 3

输出：4

解释：F(1) + F(2) + F(3) = 1 + 1 + 2 = 4

示例 2：

输入：n = 6

输出：20

思路：

我们发现斐波那契数列的第 n 项可以由第 n-1 项和第 n-2 项相加得到，因此用迭代求解，并存储倒数两项的值。

function sum(n) {
  let x = 0, y = 1, i = 1, ans = 1;
  while (i < n) {
    ans += x + y;
    [x, y] = [y, x + y];
    i++;
  }
  return ans;
}

由于 F(n) = F(n + 2) - F(n + 1)，因此有：

S(n) = F(n) + F(n - 1) + ... + F(1)
     = F(n + 2) - F(n + 1) + F(n + 1) - F(n) + ... + F(3) - F(2)
     = F(n + 2) - F(2)
     = F(n + 2) - 1

因此可以直接求出 F(n + 2)，然后减 1 即可。

function sum(n) {
  return F(n + 2) - 1;

  function F(n) {
    if (n <= 2) return 1;
    return F(n - 1) + F(n - 2);
  }
}