数组前置知识

数组：存放在连续内存空间上的相同类型数据的集合
● 数组下标从0开始的
● 数组内存空间的地址是连续的
由于连续的内存空间的地址，在增删元素时要移动其他元素的地址

二分查找

● 有序数组
● 无重复元素

//闭区间
class Solution {
    public int search(int[] nums, int target) {
 int l=0,r=nums.length-1;
 while(l<=r){
     int m=l+(r-l)/2;
     if(nums[m]==target){
        return m;
     }
     else if(nums[m]>target){
        r=m-1;
     }
     else if(nums[m]<target){
        l=m+1;
     }

 }
 return -1;
    }
}

//左闭右开
class Solution{
    public int search(int[] nums,int target){
       int l=0,r=nums.length;
       while(l<r){
          int m=l+(r-l)/2;
          if(nums[m]==target){
             return m;
          }
          if(nums[m]<target){
             l=m+1;
          }
          if(nums[m]>target){
             r=m;//此处左闭右开！
          }
       }
       return -1;
    }
}

● 时间复杂度：O(log n)
● 空间复杂度：O(1)

移除元素

● 快指针：寻找不含有目标元素的数组元素，范围
● 慢指针：指向新数组下标的位置

class Solution {
    public int removeElement(int[] nums, int val) {
        int s=0,f=0;
        int n=nums.length;
        while(f<n){
            if(nums[f]!=val){
                nums[s]=nums[f];
                s++;
            }
            f++;
        }
        return s;
    }
}//快指针使用for使代码更加简洁

● 时间复杂度：O(n)
● 空间复杂度：O(1)

有序数组的平方

//双指针：一前一后
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n=nums.length;
        int[] ans=new int[n];
        for(int i=0,j=n-1,k=n-1;i<=j;k--){
            if (nums[i]*nums[i]<nums[j]*nums[j]){
                ans[k]=nums[j]*nums[j];
                j--;
            }
            else {
                ans[k]=nums[i]*nums[i];
                i++;
            }
        }
        return ans;
    }
}

● 时间复杂度：O(n)

长度最小的子数组

● 滑动窗口起始位置：若当前窗口的值大于等于s，窗口向前移动（缩小）
● 滑动窗口结束位置：结束位置是遍历数组的指针，即for循环里的索引

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l=0,s=0;
        int n=nums.length;
        int ans=Integer.MAX_VALUE;
        for(int r=0;r<n;r++){
            s+=nums[r];
            while(s>=target){
                ans=Math.min(ans,r-l+1);
                s-=nums[l++];
            }
        }
        return ans==Integer.MAX_VALUE?0:ans;
    }
}

● 时间复杂度：O(n)
● 空间复杂度：O(1)

螺旋矩阵

class Solution {
    public int[][] generateMatrix(int n) {
        int l=0,t=0,r=n-1,b=n-1,num=1;
        int target=n*n;
        int[][]mat=new int[n][n];
        while(num<=target){
        for(int i=l;i<=r;i++){
            mat[t][i]=num++;//注意是行列，第一行，第几列
        }
        t++;
        for(int i=t;i<=b;i++){
            mat[i][r]=num++;
        }
        r--;
        for(int i=r;i>=l;i--){
            mat[b][i]=num++;
        }
        b--;
        for(int i=b;i>=t;i--){
            mat[i][l]=num++;
        }
        l++;
        }
        return mat;
    }
}

LeetCode-数组