一：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; } };
leetcode常用算法、二：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的字符子串。然后移動慢指針縮減窗體。代碼：
leetcode算法，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指向Bwindow[s[slow]]--;slow++;}if(minLen > fast - slow + 1){ minLen = fast - slow + 1;result = s.substr(slow, minLen);}window[s[slow]]--; // 縮減窗體slow++;lettercounts --;}}}return result;}
};leetcode java？三：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.
分析：這道題目也是滑動窗體，滑動窗體一般都是定義一個slow指針，然后一個fast指針不斷向前滑動(循環遍歷)。這個過程中我們要推斷1：是否找到了窗體，2：窗體時否滿足要求 3：窗體縮減等
leetcode c語言，此題也是，設置慢指針l，和快指針i遍歷，窗體過大就縮減，判斷找到的窗體是否滿足要求，技巧是用到了關聯容器的lower_bound函數，假設滿足要求就返回true，否則返回false。
這里用set或者multiset都一樣.。
。注意這里的auto是c++11的新特性。能夠用來自己主動類型判斷！
leetcode反轉鏈表。
class Solution {
public:/*bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {if(nums.size() < 2 || k == 0) return false;multiset<long> windows; // 滑動窗體int l = 0;for(int i = 0; i < nums.size(); i++){if(i - l > k){ // 窗體大小超過了k 則須要刪除nums[l]而且l++windows.erase(nums[l++]);}auto it = windows.lower_bound((long)nums[i] - (long)t);if(it != windows.end() && *it <= ((long)nums[i]+(long)t)) // 用long防止+1溢出return true;windows.insert(nums[i]);}return false;}*/bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {if(nums.size() < 2 || k == 0) return false;set<long> windows; // 滑動窗體int l = 0; // 慢指針for(int i = 0; i < nums.size(); i++){if(i - l > k){ // 窗體大小超過了k 則須要刪除nums[l]而且l++ 窗體須要縮減了windows.erase(nums[l++]);}auto it = windows.lower_bound((long)nums[i] - (long)t); // 即為nums[i]-t與nums[i]+t之間是否有元素 if(it != windows.end() && *it <= ((long)nums[i]+(long)t)) // 用long防止+1溢出 找到了return true;windows.insert(nums[i]); // not found}return false;}
};leetcode c++、
