前言🌧️

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

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

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

题目🦀

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循环就行了～

• 采用双指针
• 拿这个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-四数之和⚡️ 就结束了，算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱🔥，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。