有序数组的平方

题目描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路解析

此题很容易想到暴力解法，只需要先平方再排序即可，但是那样的话时间复杂度最快是O(nlogn)，不够好，像这样的题追求的基本都是线性的时间复杂度。

注意到对于非负值来说，其原来的顺序就是平方后的顺序，可能改变的就是负数平方之后会插入在这些非负数平方之间。另外，负数越小，平方之后就越大，插入的位置就越往后。所以我们想到用双指针的方法，设置一前一后两个指针，前指针指向要插入的负数，后指针指向负数平方后将要插入的位置。

基本的代码逻辑是，右指针不断向左移动找插入位置，左指针一个个插入右指针找好的位置，直到左指针与右指针相遇后传入最后一个值随后退出循环。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> sortedSquares(vector<int>& nums) {
	int pl = 0, pr = nums.size() - 1;
	int k = nums.size() - 1;
	vector<int> ans(nums.size());
	
	while (pl <= pr){
		while (nums[pr] > abs(nums[pl])) {
			ans[k--] = nums[pr] * nums[pr];
			pr--;
		}
	// 此时pr指向第一个小于或等于pl指向的绝对值的值
		ans[k--] = nums[pl] * nums[pl];
		pl ++;
	}
	return ans;

}

注意这里的while (pl <= pr)以及nums[pr] > abs(nums[pl])的符号差异，后者保证循环下来pr指最大的小于或等于abs(nums[pl])的值，前者保证当首尾指针交叉时数据会被写入新数组。

长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

  • 输入：s = 7, nums = [2,3,1,2,4,3]
  • 输出：2
  • 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

思路解析

此题需要注意的一个很重要的点是连续，刚开始没注意连续，想着直接给数组排序了。如果是连续的话，就需要设置指针来探究了。暴力法很好想，全部元素遍历一遍，对于每一个遍历的元素都求一个连续子数组，记录这个过程中的最小数组长度即可。

但是本题可以用双指针的方法实现线性的时间复杂度，昨天的消除连续指针是用快慢指针，上一题是用双向指针，这里因为需要求区间长度，所以想到用两个指针维护一个“窗口”。从左到右滑动这个窗口，我们设置右指针为遍历指针，然后利用贪心思想，左指针每次都指向能满足条件的最大下标处，通过这样的方式来计算出最短的区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
int minSubArrayLen(int target, vector<int>& nums) {
	int l = 0, r = 0;
	int sum = 0;
	int minLen = INT32_MAX;
	for(r;r < nums.size();r++){
		sum += nums[r];
		while (sum >= target){
			sum -= nums[l++]; // 贪心右移
			minLen = minLen < (r - l + 1 + 1)?minLen:(r-l+1 + 1);
		}
	}
	return minLen == INT32_MAX?0:minLen;
}

代码中的贪心右移是精髓，其实反过来，把左边的指针作为遍历指针，右边的指针作为贪心指针也可以，所以说这种双指针的思想就是一个遍历指针，一个贪心指针。

螺旋矩阵II

题目描述

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

思路解析

此题没有涉及算法，主要是模拟过程，其中涉及很多边界判断，需要细心发掘规律，耐心编程即可。

当n为3的时候，首先将外圈填完，可以看到最终填入的数字是$n^2 - 1$,然后填$n^2$;当n $=$ 5时,首先填外圈(边长为5)，然后填边长为3的内圈(起点是(1,1))，最后填边长为1的格子。

由此可以发现规律，边长逐渐变小，每次减2，起点逐渐增大，每次递增1，并且只要确定了边长和起点，就可以确定该圈填入的所有数字,可以根据这一点来写循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> generateMatrix(int n) {
	vector<vector<int>> ans(n,vector<int>(n));
	int st = 0;
	int k = 0;
	for (int i = n; i > 0; i-=2,st++){
		for (int offs = st; offs < st + i; offs++)
			ans[st][offs] = ++k;
		for (int offs = st + 1; offs < st + i; offs++)
			ans[offs][st + i - 1] = ++k;
		for (int offs = st + i - 1 - 1; offs >= st; offs--)
			ans[st + i - 1][offs] = ++k;
		for (int offs = st + i - 1 - 1; offs > st; offs--)
			ans[offs][st] = ++k;
	}
	return ans;

}

需要额外注意的是，在我们以右-下-左-上的顺序填入的时候，当向右填完后不能从行为st开始填，这样会覆盖掉刚刚填的内容，需要从st + 1开始，其他方向同理。