十 算法-Array

数组

1. 二分法

704

这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当大家看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了

var search = function(nums, target) {
    let n=nums.length
    let left=0, right=n-1
    while(left<=right){
        let mid=Math.floor(left+ (right-left)/2) // let mid = (l + r) >> 1; 等价于二进制数往右移一位
        if(nums[mid]==target){
            return mid
        }else if(nums[mid]<target){
            left=mid+1
        }else{
            right=mid-1
        }
    }
    return -1
};

2. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

有的同学可能说了，多余的元素，删掉不就得了。

要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

var removeElement = function(nums, val) {
    let k=0 
    for(let i=0;i<nums.length;i++){
        if(nums[i]!=val){
            nums[k]=nums[i]
            k++
        }
    }
    return k // 快指针是i，慢指针是k
};
// 双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
// 定义快慢指针
// 快指针：寻找新数组的元素(寻找过程遍历所有元素)，而新数组就是不含有目标元素的数组
// 慢指针：指向更新新数组下标的位置

3. 有序数组的平方

977

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

办法（1）每个数平方之后，排个序，美滋滋，(2) 使用双指针：数组其实是有序的，只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

// 输入：nums = [-4,-1,0,3,10]
// 输出：[0,1,9,16,100]
// 解释：平方后，数组变为 [16,1,0,9,100]
// 排序后，数组变为 [0,1,9,16,100]
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    let n=nums.length
    let result=new Array(n)
    let k=n-1
    for(let i=0,j=n-1;i<=j;){
        if(Math.pow(nums[i],2)>Math.pow(nums[j],2)){
            result[k--]=Math.pow(nums[i++],2)
        }else{
            result[k--]=Math.pow(nums[j--],2)
        }
    }
    return result
};

4. 长度最小的子数组|滑动窗口

209

给定一个含有 n 个正整数的数组和一个正整数 target 。

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

解法一：暴力解法，这道题目暴力解法当然是两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)。

解法二：滑动窗口，所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let result=Infinity // 最终结果的长度
    let subLength=0 // 子序列的长度
    let sum=0 // 子序列之和
    let s=0 // 开始的指针
    for(let e=0;e<nums.length;e++){// e结束的指针
        sum+=nums[e]
        while(sum>=target){
            subLength=e-s+1
            result=Math.min(result,subLength)
            sum-=nums[s++]
        }
    }
    return result==Infinity?0:result
};

5. 螺旋矩阵II

59 54

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

二维数组创建方法：

let result = Array.from(new Array(n), () => new Array(n))
let result = new Array(n).fill(new Array(n))

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    if(n==1){
        return [[1]]
    }
    let left=0, right=n-1, top=0, bottom=n-1
    let direction='right'
    let result = Array.from(new Array(n), () => new Array(n))
    let i=1
    while(left<=right&&top<=bottom){
        if(direction=='right'){
            for(let j=left;j<=right;j++){
                result[top][j]=i
                i++
            }
            top++
            direction='down'
        }else if(direction=='down'){
            for(let j=top;j<=bottom;j++){
                result[j][right]=i
                i++
            }
            right--
            direction='left'
        }else if(direction=='left'){
            for( let j=right;j>=left;j--){
                result[bottom][j]=i
                i++
            }
            bottom--
            direction='top'
        }else if(direction=='top'){
            for(let j=bottom;j>=top;j--){
                result[j][left]=i
                i++
            }
            left++
            direction='right'
        }
    }
    return result
};