数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学旋转数组中给定长度的连续子数组最大和查询的JavaScript程序
旋转数组意味着我们会得到一个数字，我们必须按照循环顺序向右或向左移动数组的元素。这里没有具体说明，因此我们将使用右旋转作为标准，在给定次数的旋转后，我们将返回具有最大和的子数组。我们将在文章中看到带有适当解释的代码。
问题介绍
在这个问题中，我们得到一个包含整数的数组和另一个包含查询对的数组。查询数组的每个索引包含两个整数，第一个表示当前数组旋转的次数，第二个整数表示所需子数组的长度。例如：
如果给定数组为 [5, 7, 1, 4, 3, 8, 2]，查询如下：
Queries: 3 rotations and size 3 After the three rotations, the array looks like: 3, 8, 2, 5, 7, 1, 4 From the above array, the result is 15 by subarray: 8, 2, and 5. Queries: 2 rotations and size 4 After the two rotations, the array looks like: 8, 2, 5, 7, 1, 4, 3 From the above array, the result is 22 by subarrays 8, 2, 5, and 7
让我们转向解决这个问题的方法。
朴素方法
朴素方法很简单，我们将使用两个for循环来实现给定的问题。首先，我们将遍历数组并将其顺时针旋转给定次数。然后，我们找到给定大小的子数组以及具有最大和的子数组。让我们看看它的代码：
示例
// function to rotate the array and find the subarray sum
function subSum(arr, rotations, size){
var n = arr.length
var temp = new Array(n)
var j = 0;
for(var i = n-rotations; i<n;i++){
temp[j] = arr[i];
j++;
}
for(var i = 0; i < n-rotations; i++){
temp[j] = arr[i];
j++;
}
// getting the size of the first window of the given size
var ans = -1000000000;
for(var i = 0; i<=n-size; i++) {
var cur = 0;
for(var j = i; j < i+size; j++) {
cur += temp[j];
}
if(ans < cur) {
ans = cur;
}
}
console.log("The maximum sum or given subarray with size " + size + " after " + rotations + " number of rotations is " + ans);
}
// defining array
var arr= [5, 7, 1, 4, 3, 8, 2]
// defining quries
var queries = [[3,3], [2,4]]
// traversing over the array
for(var i =0; i<queries.length; i++){
subSum(arr, queries[i][0], queries[i][1]);
}
时间和空间复杂度
上述代码的时间复杂度为 O(Q*D*N)，其中 Q 是查询数，D 是每个所需子数组的大小，N 是数组的长度。
上述代码的空间复杂度为 O(N)，因为我们使用额外的数组来存储旋转后的数组。
高效方法
这个问题可以使用滑动窗口方法以高效的方式解决。让我们直接进入这个问题的代码，并通过它进行概述：
示例
// function to rotate the array and find the subarray sum
function subSum(arr, rotations, size){
var n = arr.length
var temp = new Array(n)
var j = 0;
for(var i = n-rotations; i<n;i++){
temp[j] = arr[i];
j++;
}
for(var i = 0; i < n-rotations; i++){
temp[j] = arr[i];
j++;
}
// getting the size of the first window of the given size
var ans = -1000000000
var cur = 0;
for(var i = 0;i<size;i++){
cur += temp[i];
}
ans = cur;
for(var i = size; i<n;i++){
cur -= temp[i-size];
cur += temp[i];
if(ans < cur) {
ans = cur;
}
}
console.log("The maximum sum of given subarray with size " + size + " after " + rotations + " number of rotations is " + ans);
}
// defining array
var arr= [5, 7, 1, 4, 3, 8, 2]
// defining quries
var queries = [[3,3], [2,4]]
// traversing over the array
for(var i =0; i<queries.length; i++){
subSum(arr, queries[i][0], queries[i][1]);
}
时间和空间复杂度
上述代码的时间复杂度为 O(Q*N)，其中 Q 是查询数，N 是数组的长度。
上述代码的空间复杂度为 O(N)，因为我们使用额外的数组来存储旋转后的数组。
结论
在本教程中，我们实现了一个 JavaScript 程序，用于查询旋转数组中给定长度的连续子数组的最大和。我们实现了一个时间复杂度为 O(N*Q*D) 的朴素方法，然后使用滑动窗口的概念将其改进为 O(N*Q) 的时间复杂度，但两个代码的空间复杂度相同，均为 O(N)。
更新于：2023年4月14日
浏览量：124
广告