有序数组的平方
有一个升序的整数数组nums（其中可包含负数），返回每个数字的平方组成的新数组，要求也按升序排序。
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
我们还是沿用双指针的思路来解决，因为数组是有序的，只是因为有负数，所以会出现平方大小的问题，那么两边的平方一定是比中间的大的，所以我们定义两头，使用for循环，循环条件是始指针小于等于末指针时，执行操作。这里注意等号，比如数组只有两个元素[-2,0]，i=0,j=1，第一次执行完后，i=1,j=1,这个时候需要再执行一次，因为索引1是没有平方操作的。
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int size = nums.size() - 1;std::vector<int> result(nums.size());for(int i=0, j = size; i <= j;){if(nums[i] * nums[i] > nums[j]*nums[j]){result[size--] = nums[i] * nums[i];++i;} else {result[size--] = nums[j] * nums[j];--j;}}return result;}
};
长度最小子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
暴力解法
通过两个for循环，一个记录起始位置，一个记录末尾位置。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int min = nums.size() + 1;int current_sum = 0;int current_len = 0;for(int i = 0; i < nums.size(); ++i){current_sum = 0;current_len = 0;for(int j = i; j < nums.size(); ++j){current_sum += nums[j];++current_len;if(current_sum >= target){if(current_len < min) min = current_len;break; // 我们找的是最短子序列，找到后就可以break退出了}}}return min == n + 1 ? 0 : min;}
};
滑动窗口
依然双指针的思路，我们有一个起始位置的指针，一个末尾位置的指针。可以通过一个for循环就解决问题，问题关键是搞清楚循环中是末尾位置还是起始位置，如果说是起始位置，那么在遍历剩下的终止位置就是一个棘手的问题，我们很难确定终止位置在哪，所以for循环中定义的是终止位置。
还有一个细节就是，循环中sum >= target是用if还是while，其实很好理解，举个例子就知道了，[1,1,1,10,3],target = 10，当我们终止位置j到3索引这个位置的时候，sum和为13，这时后应该进入循环while吧，而不是if只判断一次。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int i = 0; // 左起始指针int sum = 0;int min = nums.size() + 1;int count = 0;for(int j = 0; j < nums.size(); ++j){sum += nums[j];while(sum >= target){count = j - i + 1; // 记录当前最小数组if(count < min){ min = count;}sum -= nums[i]; // 开始缩紧++i; // 更新起始位置}}return min == nums.size() + 1 ? 0 : min;}
};
在实现滑动窗口的时候，需要确定3点：
- 窗口是什么？
- 如何移动起始位置？
- 如何移动终止位置？
窗口是最小连续集合的和满足 >= target 值
起始位置需要在最小集合的和满足要求的情况下，不断的向终止位置靠拢
终止位置在不满足最小集合和的情况下，遍历数组