015_3Sum.md

15. 3Sum

---

Description

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: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) 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)

Javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
     nums.sort(function (a , b) {
         return a - b;
     });

     var result = [];
     var l = nums.length;
     if (nums[0] > 0 || nums[l - 1] < 0) {
         return result;
     }

     var dic = {};

     var i, j;
     for (i = 0; i < l - 2; i++) {
         for (j = i + 1; j < l - 1; j ++) {
             var target = 0 - nums[i] - nums[j];
            if (binarySearch(nums, j + 1, l - 1, target)) {
                var str = nums[i] + '' + nums[j] + '' + target;
                if (!dic[str]) {
                   result.push([nums[i], nums[j], target]);
                   dic[str] = 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;
};