018_4Sum.md

18. 4Sum

---

Description

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Javascript

思路： 二分查找真是神器啊！！！！！

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    if(nums.length < 4) {
        return [];
    }
    
    nums.sort(function(a, b) {
        return a - b;
    });
    
    var result = [];
    var dic = {};
    var temp;
    
    var i, j, k, l = nums.length;
    for (i = 0; i < l - 3; i++) {
        for (j = i + 1; j < l - 2; j++) {
            for (k = j + 1; k < l - 1; k++) {
                var remain = target - nums[i] - nums[j] - nums[k];
                if (binarySearch(nums, k + 1, l - 1, remain)) {
                    temp = '' +  nums[i] + nums[j] + nums[k] + remain;
                    if (!dic[temp]) {
                        result.push([nums[i], nums[j], nums[k], remain]);
                        dic[temp] = 1;
                    }
                }
            }
        }
    }
    
    return result;
};

var binarySearch = function (nums, i, j, target) {
    while (i <= j) {
        index = Math.floor( (i + j) / 2);

        if (nums[index] === target) {
            return true;
        } else if (nums[index] > target) {
            j = index - 1;
        } else {
            i = index + 1;
        }
    }
    return false;
};