【js】-【数组应用】-学习笔记

声明：本笔记是根据掘金小册总结的，如果要学习更多细节，请移步https://juejin.cn/book/6844733800300150797

1 Map 的妙用

两数求和问题

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

const twoSum = function(nums, target) {
    
    # 这里我用对象来模拟 map 的能力
    const diffs = {
    }
    
    // 缓存数组长度
    const len = nums.length
    
    // 遍历数组
    for(let i=0;i<len;i++) {
    
        // 判断当前值对应的 target 差值是否存在（是否已遍历过）
        if(diffs[target-nums[i]]!==undefined) {
    
            // 若有对应差值，那么答案get！
            return [diffs[target - nums[i]], i]
        }
        // 若没有对应差值，则记录当前值
        diffs[nums[i]]=i
    }
};

Map实现（发现，其实对象的写法更简单）

const twoSum = function(nums, target) {
    
    # 尝试Map
    const map=new Map()
    
    // 缓存数组长度
    const len = nums.length
    
    // 遍历数组
    for(let i=0;i<len;i++) {
    
        // 判断当前值对应的 target 差值是否存在（是否已遍历过）
        if(map.get(target-nums[i])!==undefined) {
    
            // 若有对应差值，那么答案get！
            return [map.get(target-nums[i]), i]
        }
        // 若没有对应差值，则记录当前值
        map.set(nums[i],i)
    }
};

2 双指针法

1. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出:
[1,2,2,3,5,6]

解题思路：

1. 分别定义两个指针，指向有效数组的最后一位，设置一个k获取num1的末尾索引
2. 开始从后往前遍历(i>0或者j>0)，将较大的那个从num1第k个位置（从后往前存）
3. 如果是num1 没有遍历完，那无需操作，若num2没有遍历完，那通过遍历把其放到num1最前面就行了
   

const merge = function(nums1, m, nums2, n) {
    
    // 初始化两个指针，分别指向num1和num2最后一位
    let i = m - 1, 
    	j = n - 1,
    	 k = m + n - 1; #初始化 nums1 尾部索引k
    	 
    // 当两个数组都没遍历完时，指针同步移动
    while(i >= 0 && j >= 0) {
    
        # 取较大的值，放到num1的最后
        if(nums1[i] >= nums2[j]) {
    
            nums1[k] = nums1[i] 
            i-- 
            k--
        } else {
    
            nums1[k] = nums2[j] 
            j-- 
            k--
        }
    }
    
    // nums2 留下的情况，特殊处理一下 
    while(j>=0) {
    
        nums1[k] = nums2[j]  
        k-- 
        j--
    }
};

2. 三数求和问题

描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

双指针法用在涉及求和、比大小类的数组题目里时，大前提往往是：该数组必须有序。否则双指针无法帮助我们缩小定位的范围。因此这道题的第一步是将数组排序：

 nums = nums.sort((a,b)=>{
    
    return a-b
})

思路：
两个关键：排序，双指针，去重

1. 先排序，当前的是i（i的范围是0-length-2），左右指针分别为j，k
2. 处理i重复的数字，跳过
3. 三数之和小于0，左指针前进（处理左指针元素重复的情况）； 三数之和大于0，右指针左移动*（处理右指针元素重复的情况）*
4. 得到目标数字组合，推入结果数组，同时左右指针都移动（同样处理左右指针元素重复的情况）

完整代码

const threeSum = function(nums) {
    
    // 用于存放结果数组
    let res = [] 
    ！1. 给 nums 排序
    nums = nums.sort((a,b)=>{
    
        return a-b
    })
    // 缓存数组长度
    const len = nums.length
    
    ！ 2.注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数
    for(let i=0;i<len-2;i++) {
    
        // 左指针 j
        let j=i+1 
        // 右指针k
        let k=len-1   
        
        ！ 3.如果遇到重复的数字，则跳过（“不重复的三元组”）
        if(i>0&&nums[i]===nums[i-1]) {
    
            continue
        }
        
        while(j<k) {
    
            ！4. 三数之和小于0，左指针前进
            if(nums[i]+nums[j]+nums[k]<0){
    
                j++
               ！4.1 处理左指针元素重复的情况
               while(j<k&&nums[j]===nums[j-1]) {
    
                    j++
                }
            } else if(nums[i]+nums[j]+nums[k]>0){
    
                // 三数之和大于0，右指针后退
                k--
               // 处理右指针元素重复的情况
               while(j<k&&nums[k]===nums[k+1]) {
    
                    k--
                }
            } else {
    
                // 得到目标数字组合，推入结果数组
                res.push([nums[i],nums[j],nums[k]])
                
                // 左右指针一起前进
                j++  
                k--
               
                // 若左指针元素重复，跳过
                while(j<k&&nums[j]===nums[j-1]) {
    
                    j++
                }  
               
               // 若右指针元素重复，跳过
               while(j<k&&nums[k]===nums[k+1]) {
    
                    k--
                }
            }
        }
    }
    
    // 返回结果数组
    return res
};

我的思考：是否直接排序＋去重 更好一些？ 发现不可以，因为如果元素有很多个0这种情况，去重就没了