讨论/技术交流/[高频题] 面试经典题目刷题笔记,一周两更/
[高频题] 面试经典题目刷题笔记,一周两更

不得不说,刷题已经和爬山、溜娃一样,成为湾区三俗,基本几个湾区的工程师碰在一起,讨论的话题总跳不出这个圈。爬山,哦不,刷题作为一个贯穿码农整个职业生涯的必须品(就算是我目前呆的微软谷歌这种养老公司也总得跳一跳,毕竟雪花的大包裹是真香啊),几年来基本每天不间断的刷,算是对这一块略有心得。帖子的前半部分想分享一些我作为面试官的常出的一些经典题目,以及题目思路的解析以及一些同类题的归纳,帖子的后半部分我会参考坛友们的留言和拍砖,来决定后面的走向

帖子会长期保持更新,只要是带娃的间隙就会偷偷上来更一下,尽量保持每周两更。

我的 VX:MSBZ1019 不管是具体的题目讨论还是给帖子的建议和拍砖,或者想进群都欢迎添加(记得加我要备注 leetcode )

5

今天来聊一道简单却十分巧妙的算法问题:算出一共有几个和为 k 的子数组。

给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

那我把所有子数组都穷举出来,算它们的和,看看谁的和等于 k 不就行了。
关键是,如何快速得到某个子数组的和呢,比如说给你一个数组 nums,让你实现一个接口 sum(i, j),这个接口要返回 nums[i..j] 的和,而且会被多次调用,你怎么实现这个接口呢?
因为接口要被多次调用,显然不能每次都去遍历 nums[i..j],有没有一种快速的方法在 O(1) 时间内算出 nums[i..j] 呢?这就需要前缀和技巧了。

展开全部 11 讨论