#牛客堂直播视频#常见面试题精讲（五）（9.9）
【本期题目】
题目一
给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组长度。例如，arr=[1,2,1,1,1]，k=3。累加和为3的最长子数组为[1,1,1]，所以结果返回3。
要求：时间复杂度O(N)，额外空间复杂度O(1)。
题目二
给定一个无序数组arr，其中元素可正、可负、可0，给定一个整数 k。求arr所有的子数组中累加和小于或等于k的最长子数组长度。例如:arr=[3,-2,-4,0,6]，k=-2，相加和小于或等于-2的最长子数组为{3,-2,-4,0}，所以结果返回4。
题目三
给定一个N*N的矩阵matrix，在这个矩阵中只有0和1两种值，返回边框全是1的最大正方形的边长长度。
例如:
01111
01001
01001
01111
01011
其中，边框全是1的最大正方形的大小为4*4，所以返回4。
题目四
给定一个整型矩阵matrix，其中的值只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量。
例如:
1110
其中，最大的矩形区域有 3 个 1，所以返回3。
再如:
1011
1111
1110
其中，最大的矩形区域有6个1，所以返回6。
题目五
有一个机器按自然数序列的方式吐出球(1 号球,2 号球,3 号球,......)，你有一个袋子，袋子最多只能装下K个球，并且除袋子以外，你没有更多的空间。设计一种选择方式，使得当机器吐出第N号球的时候(N>K)，你袋子中的球数是K个，同时可以保证从1号球到N号球中的每一个，被选进袋子的概率都是K/N。举一个更具体的例子。有一个只能装下10个球的袋子，当吐出100个球时，袋子里有10个球，并且1~100号中的每一个球被选中的概率都是10/100。然后继续吐球，当吐出1000个球时，袋子里有10个球，并且1~1000号中的每一个球被选中的概率都是10/1000。继续吐球，当吐出i个球时，袋子里有10个球，并且1~i号中的每一个球被选中的概率都是10/i，即吐球的同时，已经吐出的球被选中的概率也动态地变化。
【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者，电子工业出版社7月底将出版发行，书籍涉及算法与数据结构编程题目240道以上，并且个人实现出最优解，大部分题目为面试高频题
【参与牛客堂直播】
每周三晚8:00~9:30，直播页面http://www.nowcoder.com/live/courses
【直播题目讨论】
加入牛客3群260877110
【本期答案领取地址】
加入牛客讨论5群（272820159）
群资料中文件：2015-9-9讲座代码
淘天集团开奖9人在聊