大佬们,遇见个题没有啥思路
给定一个数组 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是否存在,存在的话左边界就可以是位置数组里的位置,右边界就是当前位置。
如果给定的数组很长,那这样的时间花费太大了
相关推荐
点赞 评论 收藏
分享
先锋战士:说得很真诚。鄙视链自古有之,学历,家庭背景,财富,权利。从小有之,小学羡慕那些当班委的,中学羡慕那些学生会的,高中羡慕尖子班拿教学金的,大学羡慕高绩点,毕业了羡慕进大厂的。工作了,又羡慕高职级的,再后来又羡慕别人早早结婚的。我想表达的观点很简单,无论是华为od还是百度,都是经历,没有孰高孰低,为了抵达下一个风景,总会付出更多东西,但不就是人生吗?正如登山,每个阶段的山,都要想办法攀登,在博主的文字中,见到了坚持和积极寻找问题解决办法的心态 点赞 评论 收藏
分享
点赞 评论 收藏
分享
