2023-12-16：用go语言，给定整数数组arr，求删除任一元素后，
新数组中长度为k的子数组累加和的最大值。
来自字节。
答案2023-12-16：
来自左程云。
灵捷3.5
大体步骤如下：
算法 maxSum1 分析：
1.计算输入数组 arr 的长度 n。
2.如果 n
3.初始化 ans 为 int 类型的最小值(math.MinInt32)。
4.对于每个数组元素 arr[i]，执行以下步骤：
4.a.删除第 i 个元素，得到新的数组 rest。
4.b.计算新数组 rest 的长度为 k 的子数组累加和的最大值，使用函数 lenKmaxSum(rest, k)。
4.c.将 ans 更新为 ans 和 lenKmaxSum(rest, k) 中的较大值。
5.返回 ans。
算法 delete 分析：
1.计算输入数组 arr 的长度 len0，即 len(arr) – 1。
2.创建一个长度为 len0 的新数组 ans。
3.初始化索引 i 为 0。
4.对于数组 arr 的每个元素 arr[j]，执行以下步骤：
4.a.如果 j 不等于给定的索引 index，则将 arr[j] 赋值给 ans[i]。
4.b.将 i 递增 1。
5.返回新数组 ans。
算法 lenKmaxSum 分析：
1.计算输入数组 arr 的长度 n。
2.初始化 ans 为 int 类型的最小值(math.MinInt32)。
3.对于每个起始位置 i，从 i 到 i + (n – k) 执行以下步骤：
3.a.初始化 cur 为 0。
3.b.对于每个元素 arr[j]，从 i 开始计数，执行以下步骤，直到计数 cnt 达到 k：
3.b. i.将 arr[j] 加到 cur 中。
3.b. ii.增加计数 cnt。
3.c.将 ans 更新为 ans 和 cur 中的较大值。
4.返回 ans。
算法 maxSum2 分析：
1.计算输入数组 arr 的长度 n。
2.如果 n
3.创建一个长度为 n 的窗口(window)数组。
4.初始化左指针 l 和右指针 r 为 0。
5.初始化变量 sum 为 0，并使用 int64 类型存储。
6.初始化 ans 为 int 类型的最小值(math.MinInt32)。
7.对于每个索引 i，从 0 到 n-1 执行以下步骤：
7.a.当窗口不为空且窗口中最后一个元素 arr[window[r-1]] 大于等于当前元素 arr[i] 时，移动右指针 r 减小窗口大小直至条件不满足。
7.b.将当前索引 i 添加到窗口中，即 window[r] = i，并递增右指针 r。
7.c.将当前元素 arr[i] 加到 sum 中。
7.d.如果 i >= k，说明窗口大小已达到 k，执行以下步骤：
7.d. i.将 ans 更新为 ans 和 sum 减去窗口左边界元素 arr[window[l]] 的较大值。
7.d. ii.如果窗口的左边界元素 arr[window[l]] 等于 i-k，说明该元素已经不在窗口内，移动左指针 l。
7.d. iii.从 sum 中减去窗口左边界元素 arr[i-k]。
8.返回 ans。
总的时间复杂度：
- maxSum1 算法的时间复杂度为 O(n^2)。
- delete 算法的时间复杂度为 O(n)。
- lenKmaxSum 算法的时间复杂度为 O(n*k)。
- maxSum2 算法的时间复杂度为 O(n)。
总的额外空间复杂度：
- maxSum1 算法的额外空间复杂度为 O(n)。
- delete 算法的额外空间复杂度为 O(n)。
- lenKma服务器托管网xSum 算法的额外空间复杂度为 O(1)。
- maxSum2 算法的额外空间复杂度为 O(n)。
go完整代码如下：
package main
import (
"fmt"
"math"
"math/rand"
"time"
)
func maxSum1(arr []int, k int) int {
n := len(arr)
if n = arr[i] {
r--
}
window[r] = i
r++
sum += int64(arr[i])
if i >= k {
ans = 服务器托管网int(math.Max(float64(ans), float64(sum-int64(arr[window[l]]))))
if window[l] == i-k {
l++
}
sum -= int64(arr[i-k])
}
}
return ans
}
func randomArray(n, v int) []int {
arr := make([]int, n)
for i := 0; i 
c++完整代码如下：
#include
#include
#include
#include
#include
using namespace std;
int lenKmaxSum(const vector& arr, int k);
int maxSum1(vector& arr, int k) {
int n = arr.size();
if (n rest(arr.begin(), arr.end());
rest.erase(rest.begin() + i);
ans = max(ans, lenKmaxSum(rest, k));
}
return ans;
}
int lenKmaxSum(const vector& arr, int k) {
int n = arr.size();
int ans = INT_MIN;
for (int i = 0; i & arr, int k) {
int n = arr.size();
if (n window(n);
int l = 0, r = 0;
long long sum = 0;
int ans = INT_MIN;
for (int i = 0; i = arr[i]) {
r--;
}
window[r] = i;
r++;
sum += arr[i];
if (i >= k) {
ans = max(ans, static_cast(sum - arr[window[l]]));
if (window[l] == i - k) {
l++;
}
sum -= arr[i - k];
}
}
return ans;
}
void randomArray(vector& arr, int n, int v) {
arr.resize(n);
for (int i = 0; i arr;
randomArray(arr, n, V);
int k = rand() % N + 1;
int ans1 = maxSum1(arr, k);
int ans2 = maxSum2(arr, k);
if (ans1 != ans2) {
cout 
c完整代码如下：
#include
#include
#include
#include
#define int64_t long long
int64_t max0(int64_t a, int64_t b) {
return (a > b) ? a : b;
}
int64_t lenKmaxSum(int64_t* arr, int64_t size, int64_t k);
int64_t maxSum1(int64_t* arr, int64_t size, int64_t k) {
if (size = arr[i]) {
r--;
}
window[r] = i;
r++;
sum += arr[i];
if (i >= k) {
ans = max0(ans, sum - arr[window[l]]);
if (window[l] == i - k) {
l++;
}
sum -= arr[i - k];
}
}
free(window);
return ans;
}
void randomArray(int64_t* arr, int64_t size, int64_t v) {
for (int64_t i = 0; i 
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: #yyds干货盘点# LeetCode程序员面试金典：寻找重复数
题目 给定一个包含 n + 1 服务器托管网个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 num…
