大佬们,遇见个题没有啥思路
给定一个数组 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是否存在,存在的话左边界就可以是位置数组里的位置,右边界就是当前位置。
如果给定的数组很长,那这样的时间花费太大了
相关推荐
05-05 12:57
门头沟学院 前端工程师
记着呢:说的很对,已经工作近7年,就是觉得年轻的时候太多忧虑,没有好好玩一玩,虽然现在我也是很多忧心事,但是真的感觉年轻的时光才是最宝贵的,玩的开心,做自己喜欢的事,全力以赴,这才是应该做的 点赞 评论 收藏
分享
