Day2 第一章 数组part02

1. 977.有序数组的平方

为什么‘非递减‘就是递增？

暴力解法就是遍历数组挨个元素平方，之后再给数组排序，这里有时间复习一下各种排序的时间复杂度以及空间复杂度！

在移除数组元素那道题里，涉及到位置变更以及要求时间复杂度为O(n)，从这可以看到一点用双指针的规律，就是：指针设定为 一前一后 或 一左一右 ，满足某一条件某一指针动。有一个主指针，就是左边的为主指针（我自己的理解），用于接收更新。相应的，副指针就是遍历找到满足某一条件的元素。

双指针

vector<int> sortedSquares(vector<int>& nums) {
	int k = nums.size() - 1;
	vector<int> result(nums.size(), 0);
	for (int i = 0, j = nums.size() - 1; i <= j;) { //注意这里i和j的增减不能在for()，需要在代码块里，因为要获取到这个元素之后才移动i和j
		if (nums[i] * nums[i] < nums[j] * nums[j]) {
			result[k--] = nums[j] * nums[j];
			j--;
		}
		else {
			result[k--] = nums[i] * nums[i];
			i++;
		}
	}
	return result;
}

2. 209.长度最小的子数组

这道题比较有意思，可以用滑动窗口的思想去理解if和while的区别。

暴力解法

int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        int subLength = 0; // 子序列的长度
        for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

int minSubArrayLen(int target, vector<int>& nums) {
	int result= INT32_MAX;
	int sum = 0;
	int i = 0;
	int subl = 0;
	for (int j = 0; j < nums.size(); j++) {
		sum += nums[j];
		while (sum >= target) {
			subl = j - i + 1;
			sum -= nums[i];
			result = result < subl ? result : subl;
			i++;
		}
	}
	return result;
}

3. 59.螺旋矩阵Ⅱ

注意左闭右开！

vector<vector<int>> generateMatrix(int n) {
	int i, j;
	int startx = 0, starty = 0;
	int middle = n / 2;
	int loop = n / 2;
	int offset = 1;
	int count = 1;
	vector<vector<int>> res(n, vector<int>(n, 0));
	while (loop--) {
		for (j = starty; j < n - offset; j++) {
			res[startx][j] = count++;
		}
		for (i = startx; i < n - offset; i++) {
			res[i][j] = count++;
		}
		for (; j > starty; j--) {
			res[i][j] = count++;
		}
		for (; i > startx; i--) {
			res[i][j] = count++;
		}
		startx++; starty++; offset += 1;
	}
	if (n % 2 == 1) {
		res[middle][middle] = count;
	}
	return res;
}

• 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
• 空间复杂度 O(1)