[leetcode javascript解题]3Sum

墨蓝 2022-07-13 02:13 177阅读 0赞

leetcode 第15题”3Sum”描述如下：

> Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.  
> **Note: The solution set must not contain duplicate triplets.**  
> For example, given array S = \[-1, 0, 1, 2, -1, -4\],  
> A solution set is:  
> \[  
> \[-1, 0, 1\],  
> \[-1, -1, 2\]  
> \]

这道题要从一个整数数组中找到三个数加起来值为0的数组集合，集合暴力解法想必很简单就是一个O（n^3）的循环，但是结果肯定是超时，无法被accepted的。一个O（n^2）的解法如下，首先把数进行从小到大排序，接着进行遍历，以当前遍历的数为target，再引入两个指针，一个指向最小数，一个指向最大数。当两数之和小于-target，移动low指针，反之移动high指针。需要注意的是为了避免重复，在选取target和移动指针时，需要增加判断条件。

/** * @param {number[]} nums * @return {number[][]} */
    var threeSum = function(nums) {
        nums.sort(function(a,b){
            return a-b;
        })
        var target,result=[],len=nums.length;
        for(var i=0;i<len;i++){
            if (target===nums[i]){
                continue;
            }
            else{
                target=nums[i];
            }
            var low=i+1,high=len-1;
            while(low<high){
                if(nums[low]+nums[high]===-target){
                    result.push([target,nums[low],nums[high]]);
                    do{
                       low++; 
                    }while(nums[low]===nums[low-1]);
                }
                else if(nums[low]+nums[high]<-target){
                    low++;
                }
                else{
                    high--;
                }
            }
        }
        return result;
    };

有什么问题欢迎与我沟通交流！