【数组】---Leetcode数组大白话

提示：本文题目跟随 代码随想录，刷题顺序。

•  前言
• ⭐️ 数组基础
• 二分查找
• • 题目
  • 何时考虑
  • 諾Leetcode 题解
• 双指针移除元素
• • 题目
  • 何时考虑
  • 諾Leetcode 题解
• 有序数组的平方
• • 题目
  • 諾Leetcode 题解
• 长度最小的子数组
• • 题目
  • 何时考虑
  • 諾Leetcode 题解
• 螺旋矩阵 II
• • 题目
  • 何时考虑
  • 諾Leetcode 题解

本文题目跟随 代码随想录，刷题顺序。对题目进行自我总结；说的不对的地方，欢迎指正。

• 存放在连续内存空间
• 不能单个元素删除，只能覆盖
• 二维数组是多条连续的内存空间

Leetcode

• 有序的

需要注意区间开闭统一

class Solution {
    public int search(int[] nums, int target) {
                    int left=0;
            int right=nums.length-1;
        if(nums[left]>target||nums[right]
          return -1;
        }
        while(left<=right){
			//这里使用位运算，相当于(right-left)/2
            int mid=left+((right-left)>>1);
                if(nums[mid]==target){
					return mid;
                }else{
					if(target>nums[mid]){
					
					    left=mid+1;
					}else{
					    right=mid-1;
					}
                }
        };
        return -1;
    }
}

Leetcode

• 不使用新对象赋值（空间复杂度位O（1））
• 暴力算法使用双循环
  这个时候可以考虑双指针

类比运输线检查鸡蛋，A->B；A把每个鸡蛋给B，B把鸡蛋依次放入仓库；
当B发现A传过来的是臭鸡蛋，丢弃，将下一次A传过来的鸡蛋顺延放入。

class Solution {
    public int removeElement(int[] nums, int val) {
        //快慢双指针处理
        if(nums==null||nums.length<=0 ){
            return 0;
            //数组长度最低为0
        };

        int twoIndex=0;
        for(int i=0;i 
        	//值不同时，会把当前值覆盖，慢指针的值    
            if(nums[i]!=val){
                nums[twoIndex]=nums[i];
                twoIndex++;
            }
        };
        return twoIndex;
    }
}

Leetcode

• 暴力算法需要遍历求平方排序
• 负数的平方会变大
• 数组两边平方相对中间大；使用双指针，注意使用下标做循环限制

双指针，一个从左向右移动，一个从右向左移动。每次比较两个平方大小。大的先存入数组，并移动指针，小的不移动。

class Solution {
    public int[] sortedSquares(int[] nums) {
        if(nums!=null){
            int[] returnNums= new int[nums.length];

            int left=0;
            int right=nums.length-1;
            int index=nums.length-1;
            //两边向中间靠拢
            while(left<=right){
                if(nums[left]*nums[left]>nums[right]*nums[right]){
                    returnNums[index]=nums[left]*nums[left];
                    left++;
                }else{
                    returnNums[index]=nums[right]*nums[right];
                    right--;
                }
                index--;
            };
            return returnNums;
        };
        return null;
    }
}

Leetcode

实际，求以每个元素开始，子数组的和第一次超过S的数组长度。取最小值，返回。

• 暴力算法使用双循环
• 连续数据
  使用滑动窗口

双指针的变种：外层一个指针变化，内层一个指针多次变化。两个指针值固定限制；
每次外层指针移动到和内层指针和大于目标值时，此时，以内层指针值对应的最小长度，然后向右移动内层指针，缩小和值。直到内层指针不移动，外层继续向右移动。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
       int minLength=Integer.MAX_VALUE;
            //暴力算法，双循环获取O（n^2）
            //双指针处理，o(n)

            int left=0;
            int sum=0;

            for(int right=0;right
                sum=sum+nums[right];
                while (sum>=target){
                    //为什么不使用if,使用while，因为sum=1+target时，减少值1时，还sum还满足条件，不移动。
                    int sumLength=right-left+1;
                    System.out.println(right+"-"+left+"-"+sumLength);
                    minLength= sumLength 
螺旋矩阵 II 
Leetcode
 
题目 
 
何时考虑 
遍历数组
每次遍历的遍历条件不变，循环不变量原则
 
諾Leetcode 题解 
 
 
一圈一圈遍历，单边外圈比内圈多2个格
奇数需要补全中心点
 
 
class Solution {
    public int[][] generateMatrix(int n) {
        //考察遍历，一圈一圈遍历
        int[][] returnNums=new int[n][n];

        //开始位置
        int Xindex=0;
        int Yindex=0;

        //能循环几圈，每圈少2个格子【前后】，所有有几个2的倍数就是能几圈
        int loopNum=n/2;

        //每圈每边，每次遍历的长度和数组长度的差值
        int offset=1;

        int num=1;

        while(loopNum>0){

            int i=Xindex;
            int j=Yindex;

            //上，从左到右
            for(;i
               returnNums[j][i]=num++; 
            };

            //右：从上到下
            for(;j
                returnNums[j][i]=num++; 
            };

            //下：从右到左
            for(;i>Xindex;i--){
                returnNums[j][i]=num++;
            };

            //左：从下到上
             for(;j>Yindex;j--){
                returnNums[j][i]=num++;
            };
            Xindex++;
            Yindex++;
            loopNum--;
            //前后都需要少一个格子，少两个格子，偏移量加2
            offset=offset+2;

        };

        //有中心点的要单独处理，即n为奇数的
        if(n%2!=0){
            int mid=(n-1)/2;
            returnNums[mid][mid]=n*n;
        };


        return returnNums;
    }
}