leetcode 2461.长度为k子数组的最大和

2024-08-24 15:28

本文主要是介绍leetcode 2461.长度为k子数组的最大和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

题目描述

示例1:

示例2:

提示:

解题思路

滑动窗口法

概念

应用场景及特点:

思路

流程展示

代码

复杂度分析


题目描述

给你一个整数数组nums和一个整数k。请你从nums中满足下述条件的全部子数组中找出最大子数组和:

  • 子数组的长度是k,且
  • 子数组中的所有元素各不相同

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件,返回0
子数组是数组中一段连续非空的元素序列。

示例1:

输入:nums = [1,5,4,2,9,9,9], k = 3
输出:15
解释:nums 中长度为 3 的子数组是:
- [1,5,4] 满足全部条件,和为 10 。
- [5,4,2] 满足全部条件,和为 11 。
- [4,2,9] 满足全部条件,和为 15 。
- [2,9,9] 不满足全部条件,因为元素 9 出现重复。
- [9,9,9] 不满足全部条件,因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和,所以返回 15 。

示例2:

输入:nums = [4,4,4], k = 3
输出:0
解释:nums 中长度为 3 的子数组是:
- [4,4,4] 不满足全部条件,因为元素 4 出现重复。
因为不存在满足全部条件的子数组,所以返回 0 。

提示:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 105

解题思路

滑动窗口法

概念

滑动窗口是一个在序列上移动的区间,通常由左右两个指针来界定这个区间的范围。通过移动指针来改变窗口的大小和位置,在窗口移动的过程中,根据问题的需求进行特定的计算和处理。

应用场景及特点

  1. 子数组 / 子串问题
  • 当需要在一个序列中找到满足特定条件的连续子数组或子串时,滑动窗口非常适用。例如,寻找和为特定值的连续子数组、含有特定字符的最长子串等。
  • 窗口的大小通常是动态变化的,根据问题的条件进行调整。
  1. 高效性
  • 相比于暴力枚举所有可能的子数组 / 子串,滑动窗口法通常能够在更短的时间内找到解。因为它利用了子数组 / 子串的连续性和窗口的滑动特性,避免了重复计算。
  1. 指针移动规则
  • 通常有两个指针,一个指向窗口的左端,一个指向窗口的右端。根据问题的具体要求,以特定的方式移动指针。
  • 例如,在寻找满足特定条件的最小子数组时,可能会先扩大窗口直到满足条件,然后再缩小窗口以找到最小的满足条件的窗口。

思路

  1. 初始化
  • 使用一个滑动窗口,窗口大小为 k
  • 创建一个计数器(可以使用 collections.Counter)来记录窗口中元素的出现次数。
  • 初始化当前窗口的和为 0,最大子数组和为 0。
  1. 滑动窗口遍历
  • 首先,将窗口的前 k 个元素加入窗口,并计算它们的和以及使用计数器记录元素出现次数。
  • 检查窗口中的元素是否各不相同。如果是,更新最大子数组和为当前窗口的和。
  • 然后,向右滑动窗口,每次将新元素加入窗口,将离开窗口的元素从计数器中移除,并更新窗口的和。
  • 再次检查窗口中的元素是否各不相同。如果是,与当前最大子数组和比较并更新。
  1. 返回结果
  • 遍历完整个数组后,返回最大子数组和。

流程展示

代码

class Solution:def maximumSubarraySum(self, nums: List[int], k: int) -> int:ans = 0cnt = Counter(nums[:k-1])s = sum(nums[:k-1])for in_,out in zip(nums[k-1:],nums):cnt[in_] += 1s += in_if len(cnt) == k:ans = max(ans, s)cnt[out] -= 1if cnt[out] == 0:del cnt[out]s -= outreturn ans

复杂度分析

  • 时间复杂度:由于只需要对数组进行一次遍历,时间复杂度为 O(n),其中 n 是数组的长度。
  • 空间复杂度:使用了计数器和有限的几个变量,空间复杂度为 O(k),其中 k 是窗口的大小。

这篇关于leetcode 2461.长度为k子数组的最大和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102865

相关文章

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系