大佬们,遇见个题没有啥思路
给定一个数组 nums 和一个目标值 k,找到和等于 k 的所有子数组。
示例 :
输入: nums = [1, -1, 5, -2, 3], k = 3
输出: [1, -1, 5, -2],[1,-1,3],[5,-2],[3]
刚开始想的是从子数组的长度开始入手,从0-nums.length,然后遍历求和
感觉这样时间复杂度会很高呀
大佬们有没有更好的思路呀
        给定一个数组 nums 和一个目标值 k,找到和等于 k 的所有子数组。
示例 :
输入: nums = [1, -1, 5, -2, 3], k = 3
输出: [1, -1, 5, -2],[1,-1,3],[5,-2],[3]
刚开始想的是从子数组的长度开始入手,从0-nums.length,然后遍历求和
感觉这样时间复杂度会很高呀
大佬们有没有更好的思路呀
全部评论 
 这不是lc15题
回溯
dfs
可以先求个前缀和数组,然后从头遍历,建立一个前缀和到位置的映射,key是前缀和,value是对应位置的数组,然后每次查询当前前缀和sum-k是否存在,存在的话左边界就可以是位置数组里的位置,右边界就是当前位置。
如果给定的数组很长,那这样的时间花费太大了
相关推荐
 点赞 评论 收藏   
分享
 苦也:佬投的是日常实习吗,是在官网投的吗,我也想找段实习沉淀一下,投了根本没消息
 点赞 评论 收藏   
分享
 