392. 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
提示：
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。
题解
很简单，每个字符串各一个指针不断向后移动比较即可
bool isSubsequence(char* s, char* t) {
int slen = strlen(s),tlen = strlen(t);
int si = 0,ti = 0;
while(si<slen && ti<tlen){
while(ti<=tlen && s[si] != t[ti]){
ti++;
}
if(ti<tlen){
si++;
ti++;
}
}
if(si == slen){
return true;
}else{
return false;
}
}
但以上代码过于复杂，其实可以直接移动 s,t 的指针最后判断 s 的指针指向的是否为 '/0' 即可
优化后代码如下:
bool isSubsequence(char* s, char* t) {
while (*s && *t) {
if (*s == *t) {
s++; // 字符相等，s后移
}
t++; // 每次比较t均后移
}
return (*s == '\0'); // 字符串s仅存有结束符，说明s是t的子序列
}
很明显的简化了代码
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
题解
int min(int a,int b){
return a<b?a:b;
}
int minSubArrayLen(int target, int* nums, int numsSize) {
int left = 0,right = 0;
int sum = 0;
int minlen = numsSize + 1;
while(right < numsSize){
sum += nums[right++];
while(sum >= target){
minlen = min(minlen,right-left);
sum -= nums[left++];
}
}
return minlen>numsSize?0:minlen;
}
//滑动窗口
滑动窗口先增加窗口的 right, 满足条件后增加 left 缩小窗口直至不满足条件，如此只需遍历一次 (将窗口从左滑到右) 即可遍历所有可能情况，时间复杂度为 O (n);
当然滑动窗口法是该题比较优秀的算法，考虑到通用性，这里还有一种时间复杂度为 O (nlogn) 的算法，具体思路为创建一个前缀和数组 O (n)，然后通过二分查找 (logn) 确定每个前缀和的满足最小条件的另一个前缀和，从中取得最小值即为结果，总时间复杂度即为 O (nlogn). 当然该算法除时间会随数据规模的增大而增大，还需额外的空间及二分的计算，增加了计算与内存的使用，因此不推荐使用。
