数组合并求和

题目描述

给定数组 arr = [ [ 2, 6, -1 ], [ 1, 5 ], [ 7, 7, [ 2, 3 ] ] ]，请实现一个函数 flatSum，调用 flatSum(arr) 返回结果为 32 ，即将给定 arr 完全扁平化并求和。

解法一：递归

思路

可以将数组 arr 分为两部分，分别计算左半部分和右半部分的和，然后将两部分的和相加。

代码

function flatSum(arr: any[]): number {
  return arr.reduce((prev, curr) => {
    if (Array.isArray(curr)) {
      return prev + flatSum(curr);
    } else {
      return prev + curr;
    }
  }, 0);
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 arr 的长度。
• 空间复杂度：O(1)。

解法二：栈

思路

可以将数组 arr 中的每个元素依次入栈，如果栈顶元素是数组，则将栈顶元素出栈并将其元素依次入栈，直到栈顶元素不是数组为止。

代码

function flatSum(arr: any[]): number {
  const stack = [...arr];
  let sum = 0;

  while (stack.length) {
    const top = stack.pop();

    if (Array.isArray(top)) {
      stack.push(...top);
    } else {
      sum += top;
    }
  }

  return sum;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 arr 的长度。
• 空间复杂度：O(n)。