53. 最大子序和

题目描述 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。 https://leetcode-cn.com/problems/maximum-subarray/ 解法1 – 使用DP,O(n) 我们定义一维数组|dp| = |nums|,dp[i]表示必须使用nums[i]元素,得到的连续子数组的最大和。那么有dp[i] = max(nums[i], dp[i – 1] + nums[i])。 解释一下,如果前面累积的最大和是负数,那么使用累积的和与nums[i]相加会使得和更小,我们还不如直接使用nums[i]作为新的连续子数组。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 我们观察到dp[i]只依赖于dp[i-1],因此我们可以使空间复杂度压缩到O(1)。 解法2 – 分治法,O(nlogn) 我们定义函数maxSubArray(nums, l, r),表示区间[l, r]内找到的连续子数组的最大和。那么在区间[l, r]内的连续子数组最大和有3种来源: 来源于[l, m) (m = (l + r) / 2),记为max1; 来源与(m, r],记为max2; 来源于跨中间元素m的区间,记为max3 那么[l, r]区间的连续子数组最大和有max(max1, max2, max3)。其中,第3种情况比较复杂。我们需要从m的左右两侧出发,通过扫描来求和,如图1所示。 我们递归求解区间[l,…

Read more

209. 长度最小的子数组

题目描述 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例:  输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 https://leetcode-cn.com/problems/minimum-size-subarray-sum/ 解法1 – 朴素算法O(n^2) 解法1使用朴素算法,我们使用指针i, j(0<=i<=j<|nums|)来描述子数组,然后计算i到j区间元素到和,如果大于等于s则取j – i + 1作为可能到解ans;如果小于s则j右移。为了实现O(1)时间复杂度的区间求和,我们可以使用prefix sum算法预先计算前缀和。当指针i和j扫描完所有的连续区间,我们取最小的解就是答案。如果找不到子数组当和大于等与s,就返回0。 需要注意一点,当找到一对i, j我们就可以退出内层循环。因为继续找下去的子序列长度已定大于(i-j+1),否则会TLE。算法的时间复杂度为O(n^2),空间复杂度为O(n) (存放前缀和)。全部代码如下: 解法2 – 优化的朴素算法O(nlogn) 我们沿用解法1的思路,但是对寻找连续区间上进行优化。我们让i = [0, |nums|),使用二分搜索寻找j,其中i <= j < |nums|。因为我们有前缀和数组prefix,我们可以在O(logn)的时间内找到一个下界(lower bound),使得prefix[j] – prefix[i] >= s。那么,j – i +1就是其中一个解,当i遍历完整个数组时,就取最小的那个解作为答案。…

Read more

295. 数据流的中位数

题目描述 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构: void addNum(int num) – 从数据流中添加一个整数到数据结构中。 double findMedian() – 返回目前所有元素的中位数。 示例: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 进阶: 如果数据流中所有整数都在 0 到 100 范围内,你将如何优化你的算法? 如果数据流中 99% 的整数都在 0 到 100 范围内,你将如何优化你的算法? https://leetcode-cn.com/problems/find-median-from-data-stream/ 解法1 解法1采用朴素算法,我们声明数组List<Integer> nums存放新增的元素。当addNum被调用时,我们向nums合适的位置插入元素使得nums有序。当调用findMedian时,如果数组中有奇数个元素,就返回nums[|nums| / 2];否则返回(nums[|nums| / 2]…

Read more