本文主要是介绍Leetcode 76. 最小覆盖子串和Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- Leetcode 76. 最小覆盖子串
- 题目描述
- C语言题解和思路
- 解题思路
- Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
- 题目描述
- C语言题解和思路
- 解题思路
Leetcode 76. 最小覆盖子串
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2：
输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。
示例 3：
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
- m == s.length
- n == t.length
- 1 <= m, n <= 10^5
- s 和 t 由英文字母组成
进阶： 你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
C语言题解和思路
char* minWindow(char* s, char* t) {int sl = strlen(s), tl = strlen(t), left, right, count = sl + 1, start = 0;if(tl > sl){return "";}int hash[256] = {0};for(int i = 0; i < tl; i++){hash[t[i]]++;}for(left = 0, right = 0; right < sl; right++){if(hash[s[right]]-- > 0){tl--;}while(tl == 0){if(count > right - left + 1){count = right - left + 1;start = left;}if(++hash[s[left]] > 0){tl++;}left++;}}if(count != sl + 1){char *ret = (char *)malloc(sizeof(char) * (count + 1));memcpy(ret, s + start, count);ret[count] = '\0';return ret;}return "";
}
解题思路
哈希表 + 滑动窗口
首先判断字符串 t 的长度和字符串 s 的长度，如果 t 长于 s ，说明字符串 s 不可能存在容纳 t 的子串，直接返回空。
创建一个哈希表并初始化为 0 ，然后循环字符串 t ，用哈希表记录 t 的字母的种类和数量。
将左右指针初始化为 0 ，将记录最小子串的长度的变量 count 初始化为字符串 s 的长度加一。
通过滑动窗口遍历字符串 s ， right 每将一个新元素纳入窗口，都先通过哈希表判断它是否在字符串 t 中出现过，如果出现过，则使字符串 t 的长度减一。当窗口将所有的字符串 t 中出现的元素都包含在内，也就是字符串 t 的长度归 0 时，开始循环判断窗口的左边界，同时 count 不断判断左右边界的距离，也就是最小覆盖子串的长度，并记录下此时左边界的位置，循环至窗口中无法覆盖所有的字符串 t 的元素为止。
循环结束后，判断 count 是否发生变化，如果它不再比字符串 s 还长，说明字符串 s 中存在满足条件的子串，此时将该子串通过memcpy函数、记录下来的左边界的值、最小的长度，将这段字符串复制到另一个字符数组当中，在新的字符串后添加上 ‘\0’ 后返回该字符串。
如果 count 没有发生改变，返回空。
Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0 <= nums.length <= 105
- -10 ^9 <= nums[i] <= 10 ^9
- nums 是一个非递减数组
- -10 ^9 <= target <= 10 ^9
C语言题解和思路
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {int *ret = (int *)malloc(sizeof(int) * 2);ret[0] = -1;ret[1] = -1;*returnSize = 2;if(numsSize == 0 || nums[0] > target || nums[numsSize - 1] < target ){return ret;}int left = 0, right = numsSize - 1, mid;while(left <= right){mid = (left + right) / 2;if(nums[mid] == target){left = mid;right = mid;while(left - 1 >= 0 && nums[left - 1] == target){left--;}while(right + 1 < numsSize && nums[right + 1] == target){right++;}ret[0] = left;ret[1] = right;return ret;}else if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}}return ret;
}
解题思路
二分查找
首先将返回的数组 ret 初始化为-1，因为数组为有序数组，先判断数组个数是否为 0 ，数组的第一个元素是否大于 target 值，数组的最后一个元素是否小于 target 值，如果以上条件满足其一，直接返回数组 ret 。
进入循环，对数组进行二分查找，如果找到满足条件的值，将下标赋给左右指针，分别循环左右指针寻找数组中值等于 target 值的左右边界的下标，将左右下标传给数组 ret ，返回 ret 。
当二分查找完后数组仍没返回任何值，说明数组中不存在值等于 target 的元素，返回值为-1的数组 ret 。
这篇关于Leetcode 76. 最小覆盖子串和Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
