SumThree 算法

LeetCode OJ:Three Sum(三数之和)

Given an array S of n integers, are there elements abc 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)
        
        let aim = [-1, 0, 1, 2, -1, -4, 3, 8, -5, -3, 2];

        let sc = aim.sort(function(a, b){ return a - b; }), result = [];

        for ( let i = 0 ; i < sc.length - 2 ; i ++ ) {
        	result = result.concat( sumtwo ( sc.slice(i+1), 0 - sc[i] ) );
        	while ( sc[i] == sc[i + 1] ) {
        		i ++;
        	}
        }

        console.log(result);

        function sumtwo (arr, val) {
        	let begin = 0, end = arr.length - 1, ret = [];

        	while ( begin < end ) {
        		let sum = arr[begin] + arr[end];
        		if ( sum < val ) {
        			begin ++;
        		} else if ( sum > val ) {
        			end --;
        		} else {
        			ret.push( { 'a':(0 - val), 'b':arr[begin], 'c':arr[end] } );
        			begin ++; end --;
        		}
        	} 

        	return ret;
        }