代码随想录-数组

704.二分查找

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let high = nums.length - 1
    let low = 0
    while(low <= high){
        //找中间数的方法
        let mid = Math.floor( (high - low) / 2) + low
        if(nums[mid] > target){
            //不符合时记得挪位，不要把mid直接当成high 或 low
            high = mid - 1
        }else if(nums[mid] < target){
            low = mid + 1
        }else if(nums[mid] === target){
            return   mid
        }
    }
    return -1
};

27.移除元素

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    //双指针
    let slow = 0 ,fast = 0;
    //这里不减一
    for(fast = 0 ; fast < nums.length ; fast++ ){
        if(nums[fast] != val){
            nums[slow] = nums[fast]
            slow ++
        }
    }
    //为什么返回slow ？ 
    //slow储存的是不存在val的前n个值的数组下标，根据题目要求，slow后面的不需要考虑
    return slow
};

977.有序数组的平方

归并排序的应用（双指针）

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
 // 使用归并排序
    let numsOk = []
    let i = 0
    //找到正负分界点
    for(let index = 0 ; index < nums.length;index ++){
        if(nums[index] > 0){
            i = index
            // 从i开始全是正数，从0到i - 1全是负数
            break
        }
    }
    // 特殊解，数组全负/全正,平方后倒序
    if(i === 0){
        if(nums[0] > 0){
          for(i ; i < nums.length;i ++){
            numsOk[i] = nums[i]*nums[i]
        }
        }else{
          for(i ; i < nums.length;i ++){
            numsOk[i] = nums[nums.length - 1 - i]*nums[nums.length - 1 - i]
        }
        }

        return numsOk
    }

    let numsLeft = [] ,numsRight = []
    // 归并排序，先让左右分别有序
    for(let m = 0;m < i;m ++){
        numsLeft[m] = nums[i - m - 1] * nums[i - m - 1]   
    }
    //右边剩余的位数 ： nums.length - i位， 所以遍历时+1
    for(let n = 0;n < nums.length - i ; n++){
        numsRight[n] = nums[n+i] * nums[n+i]
    }
    // 双指针 m 慢，n快
    let m = 0 , n = 0 ,x = 0;
    while(m < numsLeft.length && n < numsRight.length){
      if(numsLeft[m] < numsRight[n]){
        numsOk[x] = numsLeft[m]
        x ++
        m ++
      }else{
        numsOk[x] = numsRight[n]
        x ++
        n ++
      }
    }
    for(m;m < numsLeft.length;m++){
        numsOk.push(numsLeft[m])
      }
    for(n;n < numsRight.length;n++){
        numsOk.push(numsRight[n])
      }
    return numsOk
};

209.长度最小的子数组

解法一：暴力

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    // 双指针，m慢，n快
    let m = 0,n = 0 ,add = 0,length = 0
    for(m ;m < nums.length;m ++){
        add = nums[m]
        n = m 
        // 双指针寻找target
        while(add < target && n < nums.length - 1){
          add  += nums[++ n]
        }
        // 出现了达到要求的连续数组片段
        if(add >= target){
            // 出现的次数
            length = length != 0  ? (length > (n - m + 1) ? (n - m + 1) : length) : (n - m + 1) 
        }
    }
    return length
};

解法二 ：滑动窗口（注意时间复杂度），其实就是双指针

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let start = end = 0
    let sum = 0
    let len = nums.length
    // js正无穷
    let ans = Infinity
    
    // 滑动窗口写法，本质还是双指针，只用一层循环，记录end的位置
    // 本来是加到够为止，现在是减到不够为止
    // 时间复杂度 O(n) ,(每个元素被进去被操作一次，出去被操作一次所以时间复杂度是 2 × n 也就是O(n)。
    while(end < len){
        // 记录的和
        sum += nums[end];
        while (sum >= target) {
            // 记录长度
            ans = Math.min(ans, end - start + 1);
            // 一直缩小开头
            sum -= nums[start];
            start++;
        }
        end++;
    }
    return ans === Infinity ? 0 : ans
};

59.螺旋矩阵

本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
// js定义二维数组
      let matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
      // 模拟法，定义上下左右四个边界，每次循环都收紧边界
      // 计数或值
      let k = 1
      // 四个边界
      let top = 0, buttom = n - 1, left = 0, right = n - 1;
      //k 到达n平方时结束循环
      while(k < n * n + 1){
        // 以下四个循环都遵循左闭右开原则
        // 从左到右的一行,固定行（top）
        for(let j = left ; j < right + 1; j ++){
          matrix[top][j] = k
          k ++
        }
        top ++
        // 从上到下的一列，固定列(right)
        for(let i = top; i < buttom + 1; i ++){
          matrix[i][right] = k
          k ++
        }
        right --
        // 从右到左的一行，固定行(buttom)
        for(let j = right ; j > left - 1; j --){
          matrix[buttom][j] = k
          k ++
        }
        buttom --
        // 从下到上的一列，固定列(left)
        for(let i = buttom; i > top - 1; i --){
          matrix[i][left] = k
          k ++
        }
        left ++
      }
       return matrix
};