一：Minimum Size Subarray Sum（最小长度子数组的和O(N)）
题目：
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.
分析：一開始我採用的是LIS(longest increased sequence)中的最长递增子序列中的动态规划的思想。能通过，可是时间复杂度为O(N
^2)；。；另外一种方法是採用双指针+滑动窗体的思想。时间复杂度为O(N)。 严格意义上说是2N。，比方 [1,2,3,15,3,4,5,15] s=14,,,仅仅有在15处将前面的元素又又一次加了一遍，故为2N
初始快慢指针都为0，fast指针向前移动。当slow和fast中连续字数组的和大于s时。我们就開始缩减窗体，不断的对slow进行向前移动直到sum小于s，然后再移动fast继续循环
代码：
class Solution { public: // 法一 /*int minSubArrayLen(int s, vector<int>& nums) { int result = nums.size(); bool flag = false; for(int i = 0; i < nums.size(); i++){ if(nums[i] >= s) return 1; int sum = nums[i]; for(int j = i-1; j >= 0; j--){ sum += nums[j]; if(sum >= s){ result = min(result, i-j+1); flag = true; break; } } } if(flag)return result; return 0; }*/ int minSubArrayLen(int s, vector<int>& nums) { // 滑动窗体的形式+双指针 int result = nums.size()+1; int frontPoint = 0, sum = 0; for(int i = 0; i < nums.size(); i++){ sum += nums[i]; while(sum >= s){ // 找到了窗体 result = min(result, i - frontPoint + 1); // 窗体是否满足要求 sum -= nums[frontPoint++]; // 缩减窗体 } } return result == (nums.size()+1) ?0:result; } };
二：Minimum Window Substring
题目：
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
分析：这道题刚開始我採用类似于上面滑动窗体的方法，可是每次都要推断当前字符串中是否全然包括字符串t，这个推断就会提升时间复杂度，结果导致TLE。后面參看了discuss中的方法，很巧妙，也放在这里。代码中map用来存放t字符串中的字符及出现的次数，，而window用来存放字符串t中每一个字符在字符串s中出现的次数。lettercounts是一个标记变量，当等于t.size()的时候。就表示得到了一个全然包括t的字符子串。然后移动慢指针缩减窗体。代码：
TLE：
class Solution { public: bool isContain(const string &sstr, const string &t){ for(int i = 0; i < t.size(); i++){ if(sstr.find_first_of(t[i]) == string::npos) return false; } return true; } string minWindow(string s, string t) { int result = s.size()+1, frontPoint = 0; string str=""; for(int i = 0; i < s.size(); i++){ while(isContain(s.substr(frontPoint, i-frontPoint+1) , t)){ if(result > i-frontPoint+1){ result = i-frontPoint+1; str = s.substr(frontPoint, i-frontPoint+1); } frontPoint++; } } return str; } };AC代码： class Solution { public: string minWindow(string s, string t) { string result; if(s.size() == 0 || t.size() == 0) return result; unordered_map<char, int> map; unordered_map<char, int> window; // 滑动窗体 int lettercounts = 0; // 标记变量，当等于t.size()的时候。该窗体就是一个全然包括字符串t的子串 int minLen = s.size()+1; for(int i = 0; i < t.size(); i++) // 将t放入map中。就是为了加速 map[t[i]]++; for(int fast = 0, slow = 0; fast < s.size(); fast++){ // 快慢指针，快指针不断向前移动， char c = s[fast]; if(map.find(c) != map.end()){ // window[c]++; if(window[c] <= map[c]){ // 变化lettercount变量 lettercounts ++; } if(lettercounts >= t.size()){ // 表示该窗体中已经所有包括t了 while(map.find(s[slow]) == map.end() || window[s[slow]] > map[s[slow]]){ // 对窗体进行缩减 1：slow所指向字符不在map中，2：在该子串中 //出现非常多次 如BBABC ABC slow指向B window[s[slow]]--; slow++; } if(minLen > fast - slow + 1){ minLen = fast - slow + 1; result = s.substr(slow, minLen); } window[s[slow]]--; // 缩减窗体 slow++; lettercounts --; } } } return result; } };
三：Contains Duplicate III
题目：
Given an array of integers, find out whether there are two distinct indices i and j in
the array such that the difference between nums[i] and nums[j] is
at most t and
the difference between i and j is
at most k.