Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

大家好，我是速冻鱼?，一条水系前端?，喜欢花里胡哨?，持续沙雕?
欢迎小伙伴们加我微信：sudongyuer拉你进群
关注我的公众号:前端速冻鱼一起进步，期待与大家共同成长?

前言?️

算法，对前端人来说陌生又熟悉，很多时候我们都不会像后端工程师一样重视这项能力。但事实上，算法对每一个程序员来说，都有着不可撼动的地位。

因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。

编写指令的好坏，会直接影响到程序的性能优劣，而指令又由数据结构和算法组成，所以数据结构和算法的设计基本上决定了最终程序的好坏。

题目?

18. 四数之和

难度中等

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
复制代码

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
复制代码

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

解题思路?

下面是三数之和的思路，四数之和就是在三数之和的基础上，最外层再加一层for循环就行了～

15.三数之和

采用双指针
拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。
接下来如何移动left 和right呢，如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

解题步骤?

本质就是在 15-三数之和再加一层for循环

首先对数组进行排序
排序后固定一个数 nums[j],如果 nums[j] == nums[j-1]，则说明该数字重复，会导致结果重复，所以应该跳过
排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L]和 nums[R]
计算三个数的和 sum 判断是否满足为 target，满足则添加进结果集
如果 nums[i]大于 target，则三数之和必然无法等于 target，结束循环
如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sum == target 时，nums[L] == nums[L+1]则会导致结果重复，应该跳过，L++
当 sum == target 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R–

源码?

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    let result = []
    const length = nums.length
    if(!nums || length < 4) return result
    nums.sort((a,b)=>a-b);//排序
    for(let j=0;j<length-3;j++){
        //去重j
        if(j>0&&nums[j]===nums[j-1]){
            continue
        }
    
    for(let i = j+1; i<length-2;i++){
        //大于0 另外两端的也大于0 永远不可能等于0
        // if(nums[i]>0){
        //     break;
        // }
        //去重
        if(i > j+1 && nums[i] === nums[i-1]){
            continue;
        }
        let L = i+1;
        let R = length-1;
        while(L<R){
            //求和
            const sum = nums[j] + nums[i] + nums[L] + nums[R]
            //如果等于0则收纳进result
            if(sum===target){
                result.push([nums[j],nums[i],nums[L],nums[R]]);
                //去重
                while(L<R && nums[L]===nums[L+1]){
                    L++
                }
                //去重
                while(L<R && nums[R]===nums[R-1]){
                    R--
                }
                L++
                R--
            }
            else if(sum < target){
                L++
            }
            else if(sum > target){
                R--
            }
        }
    }
    }
    return result
}
复制代码

时间复杂度:O(n^2)

空间复杂度:O(n)

结束语?

那么鱼鱼的LeetCode算法篇的「LeetCode」18-四数之和⚡️ 就结束了，算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱?，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。

github?:sudongyu

个人博客?‍?:速冻鱼blog

vx?:sudongyuer

写在最后

伙伴们，如果喜欢我的口水话给??点一个赞?或者关注➕都是对我最大的支持。

文章版权归作者所有，未经允许请勿转载。

THE END

前端