特性

数组的访问效率较高，而插入效率较低;数组是连续的内存空间，通常每一个单位的大小也是固定的，因此可以按下标随机访问

• 访问,查找 O(1)

• 删除,增加 O(n)

高频题

两数之和(简单)

//暴力解法 (On2)
const twoSum=function(nums,target){
    for(let i=0;i<nums.length;i++){
        for(let j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                return[i,j]
            }
        }
    }
}

//求差-利用map(On)
const twoSum=function(nums,target){
    const len=nums.length;
    const map=new Map()
    for(let i=0;i<len;i++){
        const diff= target-nums[i]
        if(map.has(diff)){
            return [map.get(diff),i]
        }
        map.set(nums[i],i)
    }
}

//求差-利用{}(On)
const twoSum=function(nums,target){
    //边界判断
    if(nums.length<2)return nums
    //定义一个对象用于保存数据
    const object={}
    for(let i=0;i<nums.length;i++){
        const diff=target-nums[i]
        if(object[diff]!=undefined){
            return [object[diff],i]
        }
        object[nums[i]]=i
    }
}

三数之和(中等)

题目: 给定一个包含 n 个整数的数组nums，判断 nums 中是否存在三个元素a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元

1. 暴力法-3重循环 (On3)

const threeSum = function(nums) {
    //示例 nums:  [-1, -1, 0, 1, 2, -1, -4]
    let res = [];
    //不得不一开始就给数组排序, 这样好去掉重复的三元组
    //不然就会出现这种情况: [ -1, 0, 1 ], [ 0, 1, -1 ],  还是得排序后去重
    //排好序后, 重复的元素一定在一起, 当和前边的数相等时, 说明这个数已经查找过了, 就不必查找了
    // nums.sort((a, b) => a - b);  // 测试时, 别忘打开排序
    for (let i = 0; i < nums.length; i ++ ) {
        for (let j = i + 1; j < nums.length; j ++) {
            for (let k = j + 1; k < nums.length; k ++) {
                //在一开始nums没有排序的情况下, 发现做了这些处理后, 依然无法完全避免 重复的三元组
                if ( i > 0 && nums[i] == nums[ i - 1] ) continue;
                if ( j > i + 1 && nums[j] == nums[ j - 1] ) continue;
                if ( k > j + 1 && nums[k] == nums[ k - 1] ) continue;
                
                //如果在这里给 符合条件的三个数排序, 然后对比去重符合条件的 三元组, 这样更复杂了
                //所以最后发现在 一开始给整个数组排序还是比较简单的, 复杂度低的
                if (nums[i] + nums[j] + nums[k] == 0) {
                    res.push([ nums[i], nums[j], nums[k] ]);
                };
            }
        }
    };

    return res;
};

2. 排序+左右指针(On2)

解题: 1.为了方便去重，我们首先将数组排序 2.对数组进行遍历，取当前遍历的数nums[i]为一个基准数，遍历数后面的数组为寻找数组 3.在寻找数组中设定两个起点，最左侧的left(i+1)和最右侧的right(length-1) 4.判断nums[i] + nums[left] + nums[right]是否等于0，如果等于0，加入结果，并分别将left和right移动一位 5.如果结果大于0，将right向左移动一位，向结果逼近 5.如果结果小于0，将left向右移动一位，向结果逼近

// 排序+快慢指针
const threeSum=function(nums){
        //边界判断
        if(!nums || nums.length < 3) return []
        //定义空数组
        const result=[];
        //排序
        nums.sort((a,b)=>a-b);
        for(let i=0;i<nums.length;i++){
            //跳过重复数字
            if(i&&nums[i]===nums[i-1]){continue}
            //左指针
            let left=i+1;
            //右指针
            let right = nums.length-1;
            while(left<right){
                const sum=nums[i]+nums[left]+nums[right]
                //大于0移动右指针
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else{
                    result.push([nums[i],nums[left++],nums[right--]]);
                    //跳过重复数字
                    while(nums[left]===nums[left-1]){
                        left++;
                    }
                    while(nums[right]===nums[right+1]){
                        right--;
                    }
                }
            }
        }
        return result
}

四数之和(中等)

我们可以通过大小指针来逼近结果，从而达到降低一层时间复杂度的效果。 不管是几数之和，我们都用这种方法来进行优化。

//排序+双指针 On3
const fourSum= function(nums,target){
    //排除边界情况
    if(nums.length<4){
        return [];
    }
    //排序
    nums.sort((a,b)=>a-b);
    const result=[];
    for(let i = 0;i<nums.length-3;i++){
        if(i>0&& nums[i] ===nums[i-1]){
            continue;
        }
        if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target){
            break;
        }
        for(let j= i+1; j< nums.length-2;j++){
            if(j>i+1&&nums[j]===nums[j-1]){
                continue;
            }
            let left=j+1,
            right=nums.length-1;
        while(left<right){
            const sum=nums[i]+nums[j]+nums[left]+nums[right];
            if(sum===target){
            result.push([nums[i],nums[j],nums[left],nums[right]]);
            }
            if(sum<=target){
                while (nums[left]===nums[++left]);
            }else{
                while(nums[right]===nums[--right]);
            }
        }        
      }
    }
    return result;
}

盛水最多的容器(中等)

• 暴力法（On2)

幼儿园数学题：矩形面积 = 长 * 宽

放到我们这道题中，矩形的长和宽就分别对应：

长：两条垂直线的距离 宽：两条垂直线中较短的一条的长度 双重 for 循环遍历所有可能，记录最大值。

const maxArea =function(height){
    let max =0//最大容纳水量
    for(let i =0;i<height.length;i++){      
        for(let j=i+1;j<height.length;j++){
            //当前容纳水量
            let cur =(j-i) * Math.min(height[i],height[j])
            if(cur>max){
                max=cur
            }
        }
    }
    return max
}

• 对撞指针 (On)

我们可以借用双指针来减少搜索空间，转换为双指针的视角后，回顾矩形的面积对应关系如下：

(矩形面积)容纳的水量 = (两条垂直线的距离)指针之间的距离 * (两个指针指向的数字中的较小值)两条垂直线中较短的一条的长度

设置两个指针，分别指向头和尾(i指向头，j指向尾)，不断向中间逼近，在逼近的过程中为了找到更长的垂直线：

如果左边低，将i右移 如果右边低，将j左移 有点贪心思想那味儿了，因为更长的垂直线能组成更大的面积，所以我们放弃了较短的那一条的可能性。

但是这么做，我们有没有更能漏掉一个更大的面积的可能性呢？先告诉你答案是不会漏掉。

const maxArea =function (height){
    let max =0;//最大容纳水量
    let left =0; //左指针

    let right =height.length-1; //右指针

    while (left<right){
        //当前容纳水量
        let cur =(right -left)*Math.min(height[left],height[right]);
        max=Math.max(cur,max)
        height[left]<height[right]?left ++ :right --
    }
    return max
}

合并两个有序数组（简单）

nums1 、 nums2 有序，若把 nums2 全部合并到 nums1 ，则合并后的 nums1 长度为 m+n

我们可以从下标 m+n-1 的位置填充 nums1 ，比较 nums1[len1] 与 nums2[len2] 的大小，将最大值写入 nums1[len]，即

nums1[len1]>=nums2[len2] ，nums1[len--] = nums1[len1--] ,这里 -- 是因为写入成功后，下标自动建议，继续往前比较 否则 nums1[len--] = nums2[len2--]

边界条件：

若 len1 < 0，即 len2 >= 0 ，此时 nums1 已重写入， nums2 还未合并完，仅仅需要将 nums2 的剩余元素（0…len）写入 nums2 即可，写入后，合并完成

若 len2 < 0，此时 nums2 已全部合并到 nums1 ，合并完成

// O(m+n)
const merge =function(nums1,m,nums2,n){
    let len1 =m+1,
        len2 =n-1,
        len  = m+n-1
    while(len2>=0){
        if(len1<0){
            nums1[len--]=nums[len2--]
            continue
        }
        nums1[len--]=num1[len1] >=nums[len2]? nums1[len1--]:nums[len2--]
    }    
}

移动零（简单）

• Array.splice() 这个方法使用的是js 数组中的splice方法，遍历数组，将数组中的0找到并切割掉，记录0出现的次数，最后在末尾用push方法添加0

var moveZeroes = function(nums) {
  var num = 0
  for(var i = 0; i < nums.length; i++){
      if(nums[i] === 0){
          nums.splice(i,1)
          num++
          i--
      }  
  }

  for(var j = 0; j < num; j++){
    nums.push(0)
  }

  return nums
};

• 读写指针

定义两个指针 left right, left指针始终要指向第一个0所在的位置，right则负责去去到数组中的每一个数判断其是否为0，若为0则right++，反正则令nums[left] 和 nums[right] 交换位置，并使 left++(left指针始终要指向第一个0所在的位置),最后再right++，直至right指针找到最后一个数组元素为止

var moveZeroes =function(nums){
    let left = 0
    let right =0
    let len =nums.length
    while(right<len){
        if(nums[right] !==0){
        [nums[left],nums[right]] = [nums[right],nums[left]]
        left++
        }
        right++
    }
    return nums 
}

数组中重复的数字（简单）

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

• 借用map

时间复杂度：O(n)

空间复杂度：O(n)

const findRepeatNumber= function (nums){
    const map =new Map()
    for(let i of nums){
        if(map.has(i)){
            return i
        }
        map.set(i,true)
    }
    return null
}

• 原地交换

如果没有重复的数字，遍历完后，元素 i 应该在下标为 i 的位置。

1. 遍历数组，如果当前元素值与 i 不相等，则将该元素与下标 i 对应位置的元素交换，直到相等。
2. 如果元素值与下标 i 对应位置的元素相等，则是重复的，返回该元素即可。

时间复杂度：O(n)

空间复杂度：O(1)

const findRepeatNumber=function(nums){
    for(let i =0; i<nums.length; i++){
        let cur =nums[i]
        while(cur !== i){ 
            if(nums[i]===nums[cur]) return cur
            nums[i]=nums[cur]
            nums[cur]=cur
        }

    }
    return null
}

两个数组的交集（简单）

• 借用map

1. 先明确题意，题目让我们求交集，也就是两个数组共有的元素
2. 借用 Map，遍历 nums1，将 nums1 中的元素作为 key，value 都设置为 true 填充 Map
3. 遍历 nums2，如果在 map 中出现过，也就是说在 nums1 中出现过，就是他们共有的元素，push 进 res，从 map 中删除。
4. 最后返回 res 即可

时间复杂度: O(m + n)

空间复杂度: O(m)

const intersection =function (nums1,nums2){
    if(Object.prototype.toString.call(nums1)==="[object Array]"&&Object.prototype.toString.call(nums2)==="[object Array]"){
        return null
    }
    const map =new Map()
    const res= []
    nums1.forEach(n=>{
        map.set(n,true)
    })
    nums2.forEach(n=>{
        if(map.get(n)){
            res.push(n)
            map.delete(n)
        }
    })
    return res
}

删除排序数组中的重复项（简单）

• 双指针 题目要求原地删除重复出现的元素，不要使用额外的数组空间，返回移除后数组的新长度。

先明确，这道题给我们提供的是排好序的数组，所以重复的元素必然相邻。所以实际上我们只需要将不重复的元素移到数组的左侧，并返回其对应的长度即可。

1. 借助双指针，i 从索引 0 开始，j 从索引 1 开始。
2. 当前项 nums[j] 与前一位置 nums[j - 1] 相等时，j++ 跳过重复项。
3. 当二者不相等时，意味着不是重复项，此时需要将 i 指针右移， 并将 nums[j] 复制到此时的 nums[i] 位置上，然后将指针 j 右移。
4. 重复上述过程，直到循环完成，最终返回 i + 1，因为题目要求返回长度，i 是索引位置，加 1 即所求。

const removeDuplicates =function (nums){
    const n= nums.length;
    let i =0
    if(n===0){
        return 0
    }
    for (let j=1;j<n;j++){
        if(nums[j]!== nums[j-1]){
            i++;
            nums[i]=nums[j]
        }
    }
    return i+1
}

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

移除元素(简单) (opens new window)

• 对撞指针

1. 借助双指针，left 从数组的头出发，right 从数组的尾出发，不断向中间夹逼遍历
2. 如果左指针指向的元素等于 val，将右指针指向的元素赋值到左指针的位置，右指针向左移动一步
3. 如果赋值过来的元素也等于 val，那么就继续将右指针指向的元素赋值到左指针的位置，覆盖上一步等于 val 的元素
4. 当左指针指向的元素不等于 val 时，左指针向右移动一步
5. 最后当左指针和右指针相遇时，遍历完成，返回 left 即可

const removeElement =function (nums,val){
    let left =0 ;
    let right =nums.length;
    while(left<right){
        if(nums[left]===val){
            nums[left]=nums[right -1]
            right--
        }else{
            left++
        }
    }
    return left
}
// 时间复杂度: O(n)
// 空间复杂度: O(1)

接雨水（困难）

• 暴力+备忘录(On3)

var trap = function(height) {
    if(height.length==0) return 
    let len = height.length
    let maxCapacity=0
    let l_max=[],r_max=[]
    for(let i =0;i<len;i++){
        l_max[i]=height[i];
        r_max[i]=height[i];
    }
    for(let i =1;i<len;i++){
    l_max[i]=Math.max(l_max[i-1],height[i]);
    }
    for(let j =len-2;j>=0;j--){
    r_max[j]=Math.max(r_max[j+1],height[j]);
    }
    for(let i =0;i<len;i++){
    maxCapacity+=Math.min(l_max[i],r_max[i])-height[i];
    }
    return maxCapacity;
};

• 对撞指针

var trap =function (height)
{
    let end=0;
    let l=0, r=height.length-1;
    let l_max=0,r_max=0;
    while(l<r){
        l_max=Math.max(height[l],l_max)
        r_max=Math.max(height[r],r_max)
        if(l_max<r_max){
            end+=l_max-height[l]
            l++
        }else{
            end+=r_max-height[r]
        }
    }
    return end

}

参考链接

从Chrome V8源码看JavaScript数组 (opens new window)