2022-10-10 14:59 门头沟学院 Java 发布于广东
关注
大佬们，遇见个题没有啥思路
给定一个数组 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，然后遍历求和
感觉这样时间复杂度会很高呀
大佬们有没有更好的思路呀
全部评论
Karl_hl
西安电子科技大学 Java
这不是lc15题
唱跳RAP打篮球
小米集团_算法集成
回溯
ryu59073
深圳职业技术学院 C++
dfs
lc_kevin
华东师范大学 C++
可以先求个前缀和数组，然后从头遍历，建立一个前缀和到位置的映射，key是前缀和，value是对应位置的数组，然后每次查询当前前缀和sum-k是否存在，存在的话左边界就可以是位置数组里的位置，右边界就是当前位置。
恶作剧之神阿蒙 楼主
楼主 门头沟学院 Java
如果给定的数组很长，那这样的时间花费太大了
相关推荐
05-26 15:48
浙江工业大学 Python 点赞 评论 收藏
分享
05-18 14:16
成都理工大学 C++ 努力的小明a：项目看着很眼熟，施磊老师吧，我也学的这个😋我当时是把rpc框架做成了一个分布式网盘，这是一个项目，然后muduo库做成集群即时通讯，又用QT做了个交互的客户端，这样又一个项目，然后一个轻量redis，一个CAD，总共四个项目，投了三个月就今天2月份一个小厂Qt offer，然后后面想开了，Qt啥的都能干，这个月get了个北京大厂的offer，做java后端，人生就是这么魔幻，现在就在去北京入职的路上
点赞 评论 收藏
分享
05-04 17:20
武汉大学 点赞 评论 收藏
分享