[数据结构与算法]代码随想录算法训练营第三期day02-数组02

一、T977：有序数组的平方

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

暴力法：

    import java.util.Arrays;//在力扣里导不导包都行，class略

    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            nums[i] *= nums[i];
        }
        Arrays.sort(nums);//没学过快速排序的话，该操作的时间复杂度无法推算
        return nums;
    }

暴力解法的时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度

双指针法

• 因为数组其实是有序的， 只不过负数平方之后可能成为最大数了。

  • 那数组平方的最大值一定就在数组的两端，不是最左边就是最右边，不可能是中间。

  • 此时可以考虑双指针法了，一个指向起始位置，另一个指向终止位置。

    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1 ,k = right;
        int[] arr = new int[nums.length];
//        while (left < right) {
//如果用上面这行，逻辑上感觉是有疏漏的，不过IDEA可以输出正确结果，但在力扣会显示解答错误 
        while (left <= right) {
            if(nums[left] * nums[left] >= nums[right] * nums[right]) {
                arr[k] = nums[left] * nums[left];
                ++left;
            } else {
                arr[k] = nums[right] * nums[right];
                --right;
            }
            --k;
        }
        return arr;
    }

此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。

不过空间复杂度似乎有所增加（毕竟不是原地修改数组）

二、T209：长度最小的子数组

给定一个含有?n?个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组?[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

暴力解法略

• 滑动窗口（双指针）法：

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

????????在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢？

????????首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？

????????此时难免再次陷入 暴力解法的怪圈。

????????所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。

看了一遍Carl介绍的C++思路后，实现如下：

    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length <= 0) return 0;

        int sum = 0, begin = 0;
        int subLength = 0, result = Integer.MAX_VALUE;
        for (int end = 0; end < nums.length; ++end) {
            sum += nums[end];
            while (sum >= target) {
                subLength = end - begin + 1;//Java中可以用Math.min取代subLength
                result = result < subLength ? result : subLength;
//                if (begin < end) {//这段判断会导致超出时间限制（有逻辑错误，导致了死循环）
//                if (begin <= end) {//改成<=，就又可以通过了，但其实没必要判断这个
                    sum -= nums[begin++];
//                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 :result;
    }

?? ?如上所示，本来自己按照看过的思路复现的时候还加上了 if?(begin?<?end) 判断，但仔细想过之后，发现如果判断 begin<end，存在以下问题：

1. 漏掉 begin == end，也就是subLength为1之后，sum就不再扣除，进而导致while循环变成死循环；

2. 就算，改成 begin <= end，虽然逻辑上应该是没错了，但也没有必要（能来到这里begin就绝对不可能大于end）

T59：螺旋矩阵II

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

求解本题的关键依然是要坚持循环不变量原则。

• 模拟顺时针画矩阵的过程:

  • 填充上行从左到右

  • 填充右列从上到下

  • 填充下行从右到左

  • 填充左列从下到上

由外向内一圈一圈这么画下去。

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

看了Carl的C++后自己复现，主要犯了2处错误：

    public int[][] generateMatrix(int n) {
        int[][] mat = new int[n][n];
        int startx = 0, starty = 0;
        int loop = n / 2, offset = 1;
        int count = 1;
        int i, j;

        while (loop > 0) {
            i = startx; j = starty;//1、Error：i = startx, j = starty;

            for (j = starty; j < n - offset; ++j) {
                mat[i][j] = count++;
            }

            for (i = startx; i < n - offset; ++i) {
                mat[i][j] = count++;
            }

            for (; j > starty; --j) {
                mat[i][j] = count++;
            }

            for (; i > startx; --i) {
                mat[i][j] = count++;
            }

            // if (n % 2 == 1) mat[n / 2][n / 2] = count;//2、写错位置！！

            ++startx; ++starty;//1、Error：++startx, ++starty;
            ++offset;
            --loop;
        }
        if (n % 2 == 1) {
            mat[n / 2][n / 2] = count;
        }
        return mat;
    }