首页 > 其他分享 >LeetCode 1546. 和为目标值且不重叠的非空子数组的最大数目

LeetCode 1546. 和为目标值且不重叠的非空子数组的最大数目

时间:2024-07-09 12:28:58浏览次数:22  
标签:1546 set target nums int 数组 目标值 presum LeetCode

1546. 和为目标值且不重叠的非空子数组的最大数目

给你一个数组 nums 和一个整数 target 。

请你返回 非空不重叠 子数组的最大数目,且每个子数组中数字和都为 target 。

示例 1:

输入:nums = [1,1,1,1,1], target = 2
输出:2
解释:总共有 2 个不重叠子数组(加粗数字表示) [1,1,1,1,1] ,它们的和为目标值 2 。

示例 2:

输入:nums = [-1,3,5,1,4,2,-9], target = 6
输出:2
解释:总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。

示例 3:

输入:nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出:3

示例 4:

输入:nums = [0,0,0], target = 0
输出:3

提示:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 0 <= target <= 10^6

提示 1

Keep track of prefix sums to quickly look up what subarray that sums "target" can be formed at each step of scanning the input array.


提示 2

It can be proved that greedily forming valid subarrays as soon as one is found is optimal.

 

解法:前缀和 + 哈希集 + 贪心

由于题目要求所有的子数组互不重叠,因此对于某个满足条件的子数组,如果其右端点是所有满足条件的子数组的右端点中最小的那一个,则该子数组一定会被选择。

故可以使用贪心算法:从左到右遍历数组,一旦发现有某个以当前下标 i 为右端点的子数组和为 target,就给计数器的值加 1,并从数组 nums 的下标 i+1 开始,进行下一次寻找。

为了判断是否存在和为 target 的子数组,我们在遍历的过程中记录数组的前缀和,并将它们保存在哈希表中。如果位置 i 对应的前缀和为 sumi,而 sumi−target 已经存在于哈希表中,就说明找到了一个和为 target 的子数组。

如果找到了一个符合条件的子数组,则接下来遍历时需要用一个新的哈希表,而不是使用原有的哈希表,因为要确保每次找到的子数组都与此前找到的不重合。

Java版:

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int ans = 0;
        int presum = 0;
        Set<Integer> set = new HashSet<>();
        set.add(0);
        for (int i = 0; i < nums.length; i++) {
            presum += nums[i];
            if (set.contains(presum - target)) {
                ans++;
                presum = 0;
                set.clear();
                set.add(0);
            } else {
                set.add(presum);
            }
        }
        return ans;
    }
}

Python3版:

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        ans = 0
        presum = 0
        pre = set()
        pre.add(0)
        for num in nums:
            presum += num 
            if presum - target in pre:
                ans += 1
                pre.clear()
                pre.add(0)
                presum = 0
            else:
                pre.add(presum) 
        return ans

复杂度分析

  • 时间复杂度:O(N),其中 N 为数组 nums 的长度。我们要遍历数组的每个元素,其中哈希表的插入和查询都只需要单次 O(1) 的时间。
  • 空间复杂度:O(N),因为哈希表中最多保存 O(N) 个元素。

标签:1546,set,target,nums,int,数组,目标值,presum,LeetCode
From: https://blog.csdn.net/m0_56090828/article/details/140291502

相关文章

  • 代码随想录-DAY⑤-哈希表——leetcode 242 | 349 | 202
    242思路先遍历字符串1,记录每个字符的个数,然后遍历字符串2,挨个减去字符个数,出现小于零的个数说明字符总数不重合。时间复杂度:O(n)空间复杂度:O(1)代码classSolution{public:boolisAnagram(strings,stringt){if(s.length()!=t.length()){......
  • LeetCode【跳跃游戏】
    55.跳跃游戏给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。示例 1:输入:nums=[2,3,1,1,4]输出:true解释:可以先跳1步,从下......
  • LeetCode42(接雨水)[三种解法:理解动态规划,双指针,单调栈]
    接雨水给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。这是一道困难题,难度确实有点层次.我们先来朴素思想走一波.要求能接多少雨水,我们可以具化到每个硅谷,每个硅谷能存多少雨水,那么答案就是每个硅谷的雨水所加之和.对......
  • leetcode 135.分发糖果
    题目:n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果:每个孩子至少分配到1个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。请你给每个孩子分发糖果,计算并返回需要准备的最少糖果数目。题目示例:示例1:......
  • 代码随想录算法训练营第五天|LeetCode242.有效的字母异位词 LeetCode 349. 两个数组的
    代码随想录算法训练营Day5代码随想录|LeetCode242.有效的字母异位词LeetCode349.两个数组的交集LeetCode202.快乐数LeetCode1.两数之和文章目录代码随想录算法训练营前言代码随想录原文--哈希表今天的内容真的很有挑战o(╥﹏╥)o,做了很久一、哈希表基础理论1......
  • 代码随想录算法训联营第四天|LeetCode24. 两两交换链表中的节点 LeetCode19.删除链表
    系列文章目录代码随想录算法训练营第四天:代码随想录|LeetCode24.两两交换链表中的节点LeetCode19.删除链表的倒数第N个节点面试题02.07.链表相交LeetC142.环形链表文章目录系列文章目录前言一、LeetCode24.两两交换链表中的节点1、题目链接2、题解二、LeetCod......
  • LeetCode 523. 连续的子数组和
    523.连续的子数组和给你一个整数数组 nums 和一个整数 k ,如果 nums 有一个 好的子数组 返回 true ,否则返回 false:一个 好的子数组 是:长度 至少为2 ,且子数组元素总和为 k 的倍数。注意:子数组 是数组中 连续 的部分。如果存在一个整数 n ,令整数 x......
  • LeetCode 974. 和可被 K 整除的子数组
    974.和可被K整除的子数组给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。示例1:输入:nums=[4,5,0,-2,-3,1],k=5输出:7解释:有7个子数组满足其元素之和可被k=5整除:[4,5,0......
  • [LeetCode] 134. Gas Station
    想到了提前判断和小于0的情况,懒得写,果然被阴间用例10万个加油站坑了。classSolution:defcanCompleteCircuit(self,gas:List[int],cost:List[int])->int:#1n=len(gas)ifn==1:ifgas[0]>=cost[0]:ret......
  • LeetCode 算法:岛屿数量 c++
    原题链接......