- 浏览: 130159 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
[分析]
思路1: O(N), 滑动窗口法。实现时主要考虑1)窗口何时滑动或者说窗口的左边界何时更新? 2) 最小窗口是在滑动过程中比较而得,又何时更新该值? 窗口内各元素加和要保持不小于给定的s, 一旦不小于时就是滑动窗口和更新minSize的时机,向右滑动窗口直到窗口内元素加和不小于s。
思路2: O(logN), 将问题转化为在递增数列中查找某个数。建立辅助数组sum[], sum[i]表示 num数组的前 i 个元素的加和。对于每个sum[i],在 i 后面查找子数组右边界位置使得子数组的加和 >= s, 也就是在 i 位置后面寻找位置 j 满足 sum[j] >= sum[i] + s, 满足这个关系表明 num[i] 到 num[j - 1]这段子数组加和>=s。因为sum[]是递增数组,可使用二分法查找满足要求的下标。注意到实现中的binarySearchNotLess和经典的二分算法区别就在于while循环外面的return,这里是return left,如果sum数组中找不到target,会返回第一个比target大元素的下标,如果没有则返回sum.length + 1, 调用处据此判断某个元素后面是否有加和为s的子数组。
[ref]
http://www.cnblogs.com/grandyang/p/4501934.html
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
[分析]
思路1: O(N), 滑动窗口法。实现时主要考虑1)窗口何时滑动或者说窗口的左边界何时更新? 2) 最小窗口是在滑动过程中比较而得,又何时更新该值? 窗口内各元素加和要保持不小于给定的s, 一旦不小于时就是滑动窗口和更新minSize的时机,向右滑动窗口直到窗口内元素加和不小于s。
思路2: O(logN), 将问题转化为在递增数列中查找某个数。建立辅助数组sum[], sum[i]表示 num数组的前 i 个元素的加和。对于每个sum[i],在 i 后面查找子数组右边界位置使得子数组的加和 >= s, 也就是在 i 位置后面寻找位置 j 满足 sum[j] >= sum[i] + s, 满足这个关系表明 num[i] 到 num[j - 1]这段子数组加和>=s。因为sum[]是递增数组,可使用二分法查找满足要求的下标。注意到实现中的binarySearchNotLess和经典的二分算法区别就在于while循环外面的return,这里是return left,如果sum数组中找不到target,会返回第一个比target大元素的下标,如果没有则返回sum.length + 1, 调用处据此判断某个元素后面是否有加和为s的子数组。
[ref]
http://www.cnblogs.com/grandyang/p/4501934.html
public class Solution { // Method 2 public int minSubArrayLen(int s, int[] nums) { if (nums == null || nums.length == 0) return 0; int N = nums.length; int[] sum = new int[N + 1]; sum[0] = 0; for (int i = 1; i <= N; i++) sum[i] = sum[i - 1] + nums[i - 1]; int min = N + 1; for (int i = 0; i <= N; i++) { int j = binarySearchNotLess(i + 1, N, sum[i] + s, sum); if (j <= N && min > (j - i)) min = j - i; } return min <= N ? min : 0; } // 返回target在数组中的下标,若不存在,返回如果存在的话应该在的位置 public int binarySearchNotLess(int left, int right, int target, int[] sum) { int mid = 0; while (left <= right) { mid = left + ((right - left) >> 1); if (sum[mid] < target) left = mid + 1; else if (sum[mid] > target) right = mid - 1; else return mid; } return left; } // Method 1 public int minSubArrayLen1(int s, int[] nums) { if (nums == null || nums.length == 0) return 0; int N = nums.length; int start = 0; int minSize = N + 1; int sum = 0; for (int i = 0; i < N; i++) { sum += nums[i]; while (sum >= s) { minSize = Math.min(minSize, i - start + 1); if (minSize == 1) return 1; sum -= nums[start++]; } } return minSize <= N ? minSize : 0; } }
发表评论
-
Smallest Rectangle Enclosing Black Pixels
2016-02-13 12:39 863An image is represented by a bi ... -
Leetcode - H-Index II
2015-09-06 09:39 1056Follow up for H-Index: What if ... -
Leetcode - 3Sum Smaller
2015-08-18 22:12 1444Given an array of n integers nu ... -
Leetcode - Insert Interval
2015-08-14 10:12 586[分析] 这道题思路直接,但bug free需要费些心力。第一 ... -
Leetcode - Pow(x, n)
2015-08-11 09:45 431[分析] 数值计算类型题目,二分法或者借助位运算,本题两种方法 ... -
Leetcode - sqrt(x)
2015-08-10 21:40 768[分析] 这是一道数值计算的题目,Code Ganker中指出 ... -
Leetcode - Kth Smallest Element in BST
2015-08-11 10:26 616[分析] 思路1: 递归中序遍历,返回中序遍历中的第k个数。 ... -
Leetcode - Search for a Range
2015-08-10 08:32 465[分析] 思路1: 伪二分查找。若中间元素正好是target时 ... -
二分查找算法小结
2015-08-10 08:32 921在做leetcode二分查找类 ... -
Leetcode - Search in Rotated Sorted Array II
2015-08-09 18:47 440[分析] 同Search in Rotated Sorted ... -
Leetcode - Search in Rotated Sorted Array
2015-08-09 17:47 496[分析] 这题可以看做是Find Minimum in Rot ... -
Leetcode - Find Peak Element
2015-08-09 16:56 567[分析] 暴力法,按序扫描数组,找到peak element。 ... -
Leetcode - Find Minimum in Rotated Sorted Array II
2015-08-09 12:19 781[分析] Find Minimum in Rotated So ... -
Leetcode - Search Insert Position
2015-08-09 11:06 384[分析] 经典二分查找,下面代码实现了迭代方式,可以验证,若直 ... -
Leetcode - Remove Nth Node From End of List
2015-07-27 21:09 433Remove Nth Node From End of Lis ... -
Leetcode - Remove Elements
2015-07-27 10:19 412Given an array and a value, rem ... -
Leetcode - Sliding Window Maximum
2015-07-23 09:18 521Given an array nums, there is a ... -
Leetcode - LinedListCycleII
2015-07-22 10:18 520Given a linked list, return the ... -
Leetcode - Partition List
2015-07-22 09:09 382Given a linked list and a value ... -
Leetcode - Longest Substring with At Most Two Distinct Characters
2015-07-22 08:32 508Given a string, find the length ...
相关推荐
LeetCode209_Minimum_Size_Subarray_Sum 给定一个整型数组和一个数字s,找到数组中最短的一个连续子数组, 使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值, 如:给定数组[2,3,1,2,4,3],s=7 答案为...
Subarray Sum 209 3 438 76 第二章 查找表相关问题 2-1 set的使用 Intersection of Two Arrays 349 2-2 map的使用 Intersection of Two Arrays II 350 2-3 set和map不同底层实现的区别 349 350 136 242 202 290 205 ...
Subarray Sum 滑动窗口需要记录 Leetcode Java Python Leetcode.3 Longest Substring Without Repeating Characters Leetcode.76 Minimum Window Substring Leetcode.438 Find All Anagrams in a String Pattern: ...
leetcode 530 Play-with-Algorithms 基本的算法和数据结构 来自liuyubobobo老师的课程 章节 讲解例题 课程练习题 更多扩展练习 ...Subarray Sum 209 3 438 76 713 补充1:更多数组中的问题 [无] [无] 303 121 1
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 ...LeetCode ...LeetCode ...Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
Subarray Minimum Path Sum Unique Paths Unique Paths II Longest Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###...
在LeetCode上解决第一个问题 Move Zeros 3-4 即使简单的问题,也有很多优化的思路 3-5 三路快排partition思路的应用 Sort Color 3-6 对撞指针 Two Sum II - Input Array is Sorted 3-7 滑动窗口 Minimum Size ...
leetcode中国Final450_数据结构 实际上,这个存储库包含成为优秀竞争程序员最重要的数据结构和算法。 他们的名字是: Questions ----------- *Reverse the array *Find the maximum and minimum element in an array...
leetcode中国大批 0. Count Prime 1. Reverse the array 2. Find the maximum and minimum element in an array 3. Find the "Kth" max and min element of an array 4. Given an array which consists of only 0, 1...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
Minimum Path Sum Edit Distance Decode Ways Distinct Subsequences Word Break Word Break II Dungeon Game House Robber House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - ...