首页 > 代码库 > leetcode ---双指针+滑动窗体
leetcode ---双指针+滑动窗体
一: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.
分析:这道题目也是滑动窗体,滑动窗体一般都是定义一个slow指针,然后一个fast指针不断向前滑动(循环遍历)。这个过程中我们要推断1:是否找到了窗体,2:窗体时否满足要求 3:窗体缩减等
此题也是,设置慢指针l,和快指针i遍历,窗体过大就缩减,判断找到的窗体是否满足要求,技巧是用到了关联容器的lower_bound函数,假设满足要求就返回true,否则返回false。
这里用set或者multiset都一样.。
。注意这里的auto是c++11的新特性。能够用来自己主动类型判断!
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 ---双指针+滑动窗体