JS算法题之每日一题-15.四数之和

醉前端 2020-01-26 13:35:16
原文地址:https://segmentfault.com/a/1190000021419867

![image](https://segmentfault.com/img/remote/1460000021419870 "image")

> 微信公众号:醉前端,关注可了解更多题目。

题 目

> Q:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。注意:答案中不可以包含重复的四元组。

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

答 案

const fourSum = (nums, target) => {
    let result = [];
    let len = nums.length;
    if (len < 4) {
        return result;
    }
    nums.sort((a,b) => a-b);
    for(i = 0; i < len-3; i++) {
        if (i > 0 && nums[i-1] === nums[i]) continue;
        for(j = i+1; j < len-2; j++) {
            if (j > i+1 && nums[j-1] === nums[j]) continue;
            let k = len - 1
            let c = j + 1;
            while(c < len-1 && c != k) {
                let sum = nums[i] + nums[j] + nums[c] + nums[k];
                if (c > j+1 && nums[c] === nums[c-1]) {
                    c++;
                    continue;
                }
                if (k < len-1 && nums[k] === nums[k+1]) {
                    k--;
                    continue;
                }
                if(sum === target) {
                    result.push([nums[i], nums[j], nums[c], nums[k]]);
                    c++;
                    k = nums.length - 1;
                }else if (sum < target) {
                    c++;
                }else{
                    k--;
                }
            }
        }
    }
    return result;
};

![image](https://segmentfault.com/img/remote/1460000021279250 "image")

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。