前端力扣刷题 | 5：hot100之 普通数组

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

法一：双指针

1. 初始化：
   • res 用来存储当前的最大和，初始值为负无穷大。
   • left 是子数组的左边界，但它并不在实际计算中起作用，因为 Kadane’s Algorithm 不需要显式维护左右边界。
   • sum 记录当前子数组的和。
2. 遍历数组：
   • 每次都加上当前右边界的元素 nums[right]。
   • 如果当前子数组和 sum 小于零，说明从当前元素开始的新子数组会更有可能得到更大的和，因此将 sum 重置为 0，从下一个位置重新开始子数组。
3. 返回结果：res 在循环结束后包含了最大子数组和。

var maxSubArray = function(nums) {
    let res = -Infinity;  // 用来保存最大和
    let left = 0;  // 左边界
    let sum = 0;  // 当前子数组和
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        res = Math.max(res, sum);
        // 如果当前和为负数，重置子数组的起始位置
        if (sum < 0) {
            sum = 0;
            left = right + 1;
        }
    }
    return res;
};

法二：

1. 初始化：
   • currentSum 表示当前的子数组和，初始值为第一个元素。
   • maxSum 表示到当前为止的最大子数组和。
2. 遍历数组：
   • 每次更新 currentSum 为 nums[i]（重新开始新的子数组）或 currentSum + nums[i]（继续累加当前子数组）。
   • 用 maxSum 保留全局最大值。
3. 时间复杂度： O(n)，因为只需要遍历一次数组。

var maxSubArray = function(nums) {
    let currentSum = nums[0];
    let maxSum = nums[0];
    for (let i = 1; i < nums.length; i++) {
        // 判断是加入当前元素更好，还是从当前元素重新开始
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
};

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

思路：

1. 排序：
   • 使用 sort 方法，按照每个区间的起始点升序排序。
   • 排序后，方便我们依次检查和合并重叠的区间。
2. 合并逻辑：
   • 判断当前区间是否和结果数组的最后一个区间重叠：
   • 如果不重叠，直接将当前区间加入结果数组。
   • 如果重叠，则更新最后一个区间的结束点为两者结束点的最大值。

题解：

function merge(intervals) {
    // 按区间的起始点排序
    intervals.sort((a, b) => a[0] - b[0]);

    const merged = [];
    for (const interval of intervals) {
        // 如果结果数组为空，或者当前区间与结果数组的最后一个区间不重叠
        if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
            merged.push(interval);
        } else {
            // 否则，更新最后一个区间的结束点
            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
        }
    }
    return merged;
}

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例：

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:

• 向右轮转 1 步: [7,1,2,3,4,5,6]
• 向右轮转 2 步: [6,7,1,2,3,4,5]
• 向右轮转 3 步: [5,6,7,1,2,3,4]

法一：pop+unshift

var rotate = function(nums, k) {
  for(let i=0;i<k;i++){
      let temp = nums.pop();
      console.log(temp);
      nums.unshift(temp);
  }
};

• 时间复杂度：O(k * n)，其中 n 是数组的长度，k 是旋转的次数。
• 空间复杂度：O(1)，因为我们只使用了常数空间来存储临时变量 temp。

for循环导致超时

法一的优化：splice+unshift

 var rotate = function (nums, k) {
  if (nums.length === 1) return;
  k = k % nums.length;
  let temp = nums.splice(nums.length - k, k);
  nums.unshift(...temp);
};

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例：

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

思路：

1. 前缀乘积：对于数组中的每个元素 nums[i]，它左侧的所有元素的乘积可以先存储在一个数组 left 中。left[i] 表示从 nums[0] 到 nums[i-1] 的乘积。
2. 后缀乘积：对于数组中的每个元素 nums[i]，它右侧的所有元素的乘积可以存储在一个数组 right 中。right[i] 表示从 nums[i+1] 到 nums[n-1] 的乘积。
3. 结果数组：对于每个元素 nums[i]，结果数组 answer[i] 等于 left[i] * right[i]，即排除了当前元素后的乘积。
4. 由于可以不使用额外空间来存储 right 数组，因此我们可以在一次遍历过程中计算前缀乘积和后缀乘积来优化空间复杂度。

步骤：

1. 首先计算每个元素左侧的乘积，存储在结果数组中。
2. 然后计算每个元素右侧的乘积，并且将结果直接更新到结果数组中。

题解：

var productExceptSelf = function(nums) {
    let res = new Array(nums.length);
    // 初始化结果数组：result[i] 存储左侧元素的乘积
    res[0]=1;
    for(let i=1;i<nums.length;i++){
        res[i]=res[i-1]*nums[i-1];
    }
    let right=1;    // 临时变量，用来存储右侧的乘积
    // 从右到左遍历，更新结果数组
    for(let j=nums.length-1;j>=0;j--){
        res[j]*=right;
        right*=nums[j];
    }
    return res;
};