LeetCode15.三數(shù)之和 JavaScript

idisfkj 發(fā)布于2019-08-23 14:51 / 760人閱讀

摘要：三數(shù)之和給定一個包含個整數(shù)的數(shù)組，判斷中是否存在三個元素，，，使得找出所有滿足條件且不重復的三元組。例如給定數(shù)組，滿足要求的三元組集合為答案參考

LeetCode15.三數(shù)之和 JavaScript

給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復的三元組。

注意：答案中不可以包含重復的三元組。

例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[[-1, 0, 1],[-1, -1, 2]]

答案參考：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    var result = new Array();
    var len = nums.length;
    var flag = 0;
    var hash = {};
    nums.sort((a, b) => {
        return a-b;
    });
    if(nums[0] > 0 || nums[len - 1] < 0) return result;
    for(var i = 0; i < len; i++){
        if(nums[i] === nums[i-1]) continue;
        flag = 0 - nums[i];
        var start = i + 1, end = len - 1;
        while(start < end){
            var middle = new Array();
            if(nums[start] + nums[end] < flag){
                start ++;
            } else if(nums[start] + nums[end] > flag){
                end--;
            } else {
                middle.push(nums[i]);
                middle.push(nums[start]);
                middle.push(nums[end]);
                if(!hash[middle]){
                    hash[middle] = true;
                    result.push(middle);
                }
                start += 1;
                end -= 1;
                while(start < end && nums[start] === nums[start - 1]){
                    start += 1;
                }
                while(start < end && nums[end] === nums[end + 1]){
                    end -= 1;
                }
            }
        }
    }
    return result;   
};