Leetcode刷题——7 滑动窗口双指针

注：以下代码均为c++

1. 两数之和2（输入有序数组）

在这里插入图片描述

// 法1：暴力
vector<int> twoSum1(vector<int>& numbers, int target) {vector<int> ans(2);int n = numbers.size();for(int i = 0; i < n-1; i++){if(i != 0 && numbers[i] == numbers[i-1])continue;for(int j = i + 1; j < n; j++){if(numbers[i] + numbers[j] == target){//ans[0] = i + 1, ans[1] = j + 1;//return ans;return {i + 1, j + 1};  //注意：这里可以直接这么写，不需要再建立一个vector返回}}}return {-1, -1};
}

暴力(O(n^2)) =》单调性 =》优化：双指针(O(n))
请添加图片描述

// 法2：双指针
vector<int> twoSum(vector<int>& numbers, int target){int n = numbers.size();for(int i = 0, j = n - 1; i < n-1; i++){while(numbers[i] + numbers[j] > target)j--;if(numbers[i] + numbers[j] == target)return {i + 1, j + 1};}return {-1, -1};
}

2. 合并两个有序数组

在这里插入图片描述

法1：新建一个数组存nums1，从前往后依次遍历。

void merge1(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> nums11(m);copy(nums1.begin(), nums1.begin() + m,nums11.begin());int i, j, k;for(i = 0, j = 0, k = 0; i < m && j < n; k++){if(nums11[i] <= nums2[j]){nums1[k] = nums11[i];i++;}else{nums1[k] = nums2[j];j++;}}while(i < m){nums1[k] = nums11[i];i++, k++;}while(j < n){nums1[k] = nums2[j];j++, k++;}
}

法2：不需要新建数组，直接在原数组上遍历，从后向前遍历。找到nums1和nums2中的较大数，添加到nums1末尾。
在这里插入图片描述

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){int i, j, k;for(i = m-1, j = n-1, k = m+n-1; i >= 0 && j >= 0; k--){if(nums1[i] > nums2[j]){nums1[k] = nums1[i];i--;}else{nums1[k] = nums2[j];j--;}}while(j >= 0){nums1[k] = nums2[j];k--, j--;}
}

3. 最小覆盖子串

在这里插入图片描述

法1：暴力穷举：在s中从头找所有比 t 长的字符串
法2：滑动窗口
请添加图片描述

string minWindow2(string s, string t){unordered_map<char, int> hash;  //每个元素缺多少for(auto c : t)hash[c]++;int cnt = hash.size();  //下面for循环中，c表示已经匹配的哈希表元素个数string res;  //存结果//i为右指针，j为左指针for(int i = 0, j = 0, c = 0; i < s.size(); i++){  //右指针一直向右移动，不回头if(hash[s[i]] == 1)  //找到了s[i]在哈希表内，且该元素正好缺一个：该元素完全匹配c++c++;hash[s[i]]--;//左指针右移while(hash[s[j]] < 0)  //s[j]多了，=0的时候正好hash[s[j++]]++;  //先将缺的hash值+1，再左指针右移if(c == cnt)  //都匹配了if(res.empty() || res.size() > i-j+1)res = s.substr(j, i-j+1);}return res;
}

4. 最长有效括号

在这里插入图片描述

int work(string s){int res = 0;for(int i = 0, start = 0, cnt = 0; i < s.size(); i++){  //start记录起始位置，i从前往后遍历一遍if(s[i] == '(')cnt++;else{cnt--;if(cnt < 0){start = i + 1;cnt = 0;}else if(cnt == 0)res = max(res, i - start + 1);}}return res;
}
int longestValidParentheses(string s) {int res = work(s);reverse(s.begin(), s.end());for(auto &c: s)  //将'('转换为')'，将')'转换为'('c = c ^ 1;  //查ascii码发现'('与')'的二进制只差1，也就是说最后一位一个是0一个是1，所以可以用异或操作来将0变成1，将1变成0，从而实现'('到')'的反转res = max(res, work(s));return res;
}

5. 最小栈

在这里插入图片描述

本质：求最小前缀。用一个栈保存当前最小值。

class MinStack{
public:stack<int> stk, stk_min;MinStack(){}void push(int val){stk.push(val);if(stk_min.empty())    stk_min.push(val);else stk_min.push(min(val, stk_min.top()));}void pop(){stk.pop();stk_min.pop();}int top(){return stk.top();}int getMin(){return stk_min.top();}
};