leetcode
leetcode 1901 ~ 1950
在两个数组的区间中选取数字

在两个数组的区间中选取数字

难度:

标签:

题目描述

代码结果

运行时间: 1211 ms, 内存: 83.4 MB


/*
题目思路:
我们有两个数组 `arr1` 和 `arr2`,以及一个区间 `[start, end]`。
目标是从 `arr1` 和 `arr2` 的区间 `[start, end]` 中选取数字,并按顺序返回一个新的数组。
需要注意的是:区间 `[start, end]` 是闭区间,包括 start 和 end。

使用 Java Stream 来简化数组的操作和组合。
*/

import java.util.stream.IntStream;

public class Solution {
    public int[] selectNumbers(int[] arr1, int[] arr2, int start, int end) {
        return IntStream.concat(
                IntStream.rangeClosed(start, end).map(i -> arr1[i]),
                IntStream.rangeClosed(start, end).map(i -> arr2[i])
        ).toArray();
    }
}

解释

方法:

这道题目的解法使用了动态规划(DP)与哈希表的结合。定义dp[i]为一个字典,其中键是从第一个元素到第i个元素的子数组可能的和,值是达到这个和的不同子数组的数量。对于每个元素nums1[i]和nums2[i],更新dp[i]考虑两种情况:加上nums1[i]和减去nums2[i]。为了构建dp[i],我们从dp[i-1]继承并更新。最后,我们累加所有dp[i]中和为0的情况,这代表从数组开头到当前位置的子数组和为0的数量。使用MOD来避免大数问题。

时间复杂度:

O(n^2)

空间复杂度:

O(n^2)

代码细节讲解

🦆
在动态规划解法中,为什么选择将dp[i]定义为一个字典而不是一个简单的数组?
在动态规划中,dp[i]被定义为一个字典,是因为子数组的和的范围非常广,可能从很大的负数到很大的正数,这使得使用数组来存储所有可能的和变得不切实际,因为这会要求一个非常大的数组来覆盖所有可能的索引,导致空间复杂度极高且大部分值为空。使用字典可以动态地仅存储出现过的和及其次数,这样大大减少了空间的浪费,提高了空间效率。
🦆
解法中提到了`从dp[i-1]继承并更新`,能否具体说明如何从dp[i-1]更新到dp[i]?
从dp[i-1]更新到dp[i]的过程涉及遍历dp[i-1]中记录的所有可能的和,并基于这些和通过添加当前的nums1[i]和减去当前的nums2[i]来生成新的和。对于dp[i-1]中的每个和preSum,dp[i]中preSum + nums1[i]的计数增加dp[i-1][preSum]的值,同样地,dp[i]中preSum - nums2[i]的计数也增加dp[i-1][preSum]的值。这样,dp[i]不仅包含了由dp[i-1]产生的新的可能和,还包括了仅由nums1[i]和-num2[i]产生的和。
🦆
在实现中,你如何处理当和为0时的边界情况,尤其是在数组的开始处?
在数组的开始处,即i=0时,我们单独处理nums1[0]和-num2[0],每个初始和的计数被设置为1。这意味着,即使在数组的开始,我们也考虑了子数组可以仅由一个元素组成的情况,即sum(nums1[0])和sum(-nums2[0])。从i=1开始,每个dp[i]都基于前一个dp[i-1]更新,并且每次更新时,如果和为0的情况出现,该情况被加入到最终结果中。这确保了即使是仅包含一个元素的子数组也被正确计数。
🦆
你是如何确定MOD值为10^9+7的?使用不同的MOD值对结果有什么影响?
MOD值10^9+7是一个常用的大素数,它被广泛用于避免整数溢出的同时保持计算精度,特别是在算法竞赛和计算机科学中。这个数足够大,能够确保在大多数情况下计算不会溢出,同时由于是素数,它在数论中的一些特性(如模逆元的计算)也是有利的。使用不同的MOD值可能会影响计算的正确性和性能。如果MOD较小,可能会导致更频繁的溢出和结果错误;如果MOD非素数,还可能影响某些数学运算的正确性。

相关问题