day2

1、leetcode977 有序数组的平方

1. 题目：

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

   示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

   示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

2. 思路：

   1. 暴力法：

      • step1：创建一个新数组result，用于存放原数组元素的平方值
      • step2：遍历原数组，将各个元素的平方值放入新数组
      • step3：对新数组进行排序，得到最后输出结果

      class Solution {
          public int[] sortedSquares(int[] nums) {
              int[] res = new int[nums.length];
      
              for(int i=0; i < nums.length; i++){
                  res[i] = nums[i]*nums[i];
              }
      
              Arrays.sort(res);
              return res;
          }
      }
      

      时间复杂度： O(n + nlogn)， 可以说是O(nlogn)的时间复杂度。

   2. 双指针法

      • 因为给定的数组nums为非递减序列，并且可能包含负数 ==> 因此nums数组中元素的平方值的最大值一定是从两边获得

      • 由上述推论得知，可采用双指针方法，从两端向中间逼近的方式来遍历原数组，计算两端元素的平方值并将其中的较大值放入到新的数组

        

        class Solution {
            public int[] sortedSquares(int[] nums) {
                int[] res = new int[nums.length];
                int left = 0;
                int right = nums.length - 1;
                int resIndex = res.length - 1;//因为是从两端获取最大平方值，所以从最后开始放元素
        
                while(left <= right){ //因为是采用两端向中间逼近的方式，因此退出循环的条件为left>right,这里的 = 是防止漏处理最后的元素
                    if(nums[left]*nums[left] > nums[right]*nums[right]){
                        res[resIndex] = nums[left]*nums[left];
                        resIndex--;
                        left++;
                    } else {
                        res[resIndex] = nums[right]*nums[right];
                        resIndex--;
                        right--;
                    }
                }
        
                return res;
        
            }
        }
        

        时间复杂度：O(n）

2、leetcode209 长度最小的子数组

1. 题目：

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

   示例：

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

2. 思路

   1. 暴力法

      • 使用双层for循环，最外层循环定位起始位置，里层循环定位终止位置，找到所有满足条件的子数组，每次更新子数组的长度最小值，循环结束得到输出结果。

      •  class Solution {
             public int minSubArrayLen(int target, int[] nums) {
                 int minLength = Integer.MAX_VALUE;
                 int sum = 0;
         
                 for(int i=0; i<nums.length; i++){
                     sum = 0;
                     for(int j=i; j<nums.length; j++){
                         sum += nums[j];
                         if(sum >= target){
                             minLength = Math.min(minLength,j-i+1);
                             break;//因为是找符合条件最短的子序列，所以一旦符合条件就break
                         }
                     }
                 }
         		// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
                 return minLength == Integer.MAX_VALUE ? 0 : minLength;
             }
         }
        

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

   2. 滑动窗口

      1. 什么是滑动窗口？

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

      2. 用一层for循环替代暴力法中的双层for循环，则应该保留对起始位置的遍历还是终止位置的遍历？

         • 若保留对起始位置的遍历，则后面又要一个一个去找合适的终止位置，与暴力法无异
         • 若保留对终止位置的遍历，则遍历终止位置获得满足条件的子数组，再去移动起始位置，使其在满足条件的前提下，子数组长度最小。
         • 综上，应保留对终止位置的遍历

      3. 滑动窗口的核心：如何移动起始位置

         • 滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。

      4. class Solution {
             public int minSubArrayLen(int target, int[] nums) {
                 int minLength = Integer.MAX_VALUE;
                 int start=0;
                 int sum = 0;
                 
                 for(int end=0; end<nums.length; end++){
                     sum += nums[end];
         
                     while(sum >= target){//因为起始位置向后移动是一个持续的过程，因此使用while而非if（if仅执行一次操作）
                         minLength = Math.min(minLength, end-start+1);//end-start+1:此时的子数组长度
                         sum -= nums[start];
                         start++;//先减去当前起始位置的值，再将起始位置向后移动
                     }
                 }
         
                 return minLength == Integer.MAX_VALUE ? 0 : minLength;
             }    
         
         }
         

         时间复杂度：O(n)

3、leetcode59 螺旋矩阵

1. 题目

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

   示例:

   输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

2. 思路

   • 一圈一圈地遍历，输入为n时，有n/2圈。（如果n为奇数的话，需要单独给矩阵最中间的位置赋值）

     • 每一圈按照顺时针打圈

     • 注意：每一圈中每条边的处理规则固定，坚持每条边左闭右开的原则【保证循环不变量】

       

   • class Solution {
         public int[][] generateMatrix(int n) {
             int[][] result = new int[n][n];
             int startx = 0;
             int starty = 0;
             int offset = 1;
             int loop = n/2;
             int mid = n/2;
             int count = 1;
             int i,j;
     
             while(loop-- > 0){
                 //顺时针方向，对四条边分别进行处理，保证循环不变量，坚持每条边左闭右开的原则
                 for(j=starty; j<n-offset;j++){
                     result[startx][j] = count++;
                 }
                 for(i=startx; i<n-offset; i++){
                     result[i][j] = count++;
                 }
                 for(;j>starty;j--){
                     result[i][j] = count++;
                 }
                 for(;i>startx;i--){
                     result[i][j] = count++;
                 }  
     			
                 //一圈四条边处理结束后，变换起始位置以及offset
                 startx++;
                 starty++;
                 offset++;
             }
             
     		//如果n为奇数的话，需要单独给矩阵最中间的位置赋值
             if( n % 2 == 1){
                 result[mid][mid] = count;
             }
     
             return result;
         }
     }
     

4、数组小结

1. 数组的基本概念
   • 数组是存放在连续内存空间上的相同类型数据的集合。
2. 数组特点：
   • 数组下标从0开始
   • 数组内存空间的地址连续
     • 数组的查、改操作很方便
       • 可以方便的通过下标索引的方式获取到下标对应的数据。
     • 数组的增、删操作比较麻烦
       • 增：需要开辟新的内存空间，并移动其他元素的内存空间地址。
       • 删：需要移动后面元素的内存空间地址
3. 双指针法
   1. 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
   2. 双指针时间复杂度：O(n)
4. 滑动窗口
   1. 用以解决 数组中 连续区间内 求满足一定条件的 子数组 的相关问题
5. 二分法、模型行为（例如：螺旋矩阵）都要遵守循环不变量原则。