1508.子数组和排序后的区间和

链接：1508.子数组和排序后的区间和
难度：Medium
标签：数组、双指针、二分查找、排序
简介：请你返回在新数组中下标为  left  到  right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

题解 1 - typescript

• 编辑时间：2021-05-13
• 执行用时：436ms
• 内存消耗：75.2MB
• 编程语言：typescript
• 解法介绍：排序。

function rangeSum(nums: number[], n: number, left: number, right: number): number {
  const prefixSumList: number[] = [];
  let sum = 0;
  nums.forEach(v => prefixSumList.push((sum += v)));
  const list: number[] = nums.slice();
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      list.push(prefixSumList[i] - (prefixSumList[j - 1] ?? 0));
    }
  }
  return (
    list
      .sort((a, b) => a - b)
      .slice(left - 1, right)
      .reduce((total, cur) => total + cur, 0) %
    (10 ** 9 + 7)
  );
}