当前位置：首页 > news >正文

力扣8.29

news 来源：原创 2024/9/20 17:27:48

76.最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

数据范围

m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成

分析

滑动窗口，当我们第一次找到t在s中的位置时，若长度为len，则后续的结果只需要考虑小于len的情况即可，设置一个长度为len的窗口，每次将窗口向右滑动，r指针为右边界，每次向右滑动一格，l指针为左边界，用于缩小滑动窗口，写一个check()函数判断窗口内的字符串是否包含t，若包含，则用l缩小窗口的即可。check()函数可以只使用一个map，在刚开始预处理t字符串的字符频数，s[l]在t中则对应字符频数减1，若频数均<=0则说明包含t。

代码

class Solution {
public:map<char, int> cnt;bool check() {for(auto [k, v] : cnt) {if(v > 0) return false;}return true;}void print() {for(auto [k, v] : cnt) {cout << k << " " << v << "  ";}cout << endl;}string minWindow(string s, string t) {if(s.size() < t.size()) return "";int l = 0, r = 0;for(int i = 0; i < t.size(); i ++ ) {cnt[t[i]] ++ ;}int len = 0x3f3f3f3f;int pos = -1;while(r < s.size()) {if(cnt.find(s[r]) != cnt.end()) {cnt[s[r]] -- ;}bool flag = check();while(check() && l <= r) {if(r - l + 1 < len) {len = r - l + 1;pos = l;}if(cnt.find(s[l]) != cnt.end()) cnt[s[l]] ++ ;l ++ ;}r ++ ;}if(pos == -1) return "";return s.substr(pos, len);}
};

15.三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

数据范围

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

分析

本题实际是两数之和的进阶版，最暴力的方法就是使用三重循环，复杂度为O(N^3)，由于本题和两数之和有点关系，很容易可以发现后面的两重循环可以使用一个双指针算法进行简化，思路和两数之和一模一样。本题要求三元组不重复，思考一下什么情况会重复，双指针l和r表示边界，举个例子-3、1、1、2，指针l遍历第一个1和第二个1都会产生相同的答案，若要消除这种情况，在遍历l时只要判断nums[l]和nums[l-1]是否相同即可，若相同则上一次循环已经考虑过这种情况，直接continue，同时与这种情况对应的是遍历r时两个数相同，此时判断nums[r]和nums[r+1]是否相同即可

代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;int n = nums.size();sort(nums.begin(), nums.end());for(int i = 0; i < nums.size(); i ++ ) {if(i && nums[i] == nums[i - 1]) continue;int l = i + 1, r = n - 1;while(l < r) {if(l > i + 1 && nums[l] == nums[l - 1]) {l ++ ;continue;}if(r < n - 1 && nums[r] == nums[r + 1]) {r -- ;continue;}int t = nums[l] + nums[r] + nums[i];if(t > 0) {r -- ;} else if(t < 0){l ++ ;} else {res.push_back({nums[i], nums[l], nums[r]});l ++ ;r -- ;}}}return res;}
};