js leetcode 4数之和

1.hash table做法
[0,1,2,2,-3,-3,-1,-1] --> {'0':1,'1':1,'2':2,'-1':2,'-3':2}
主要是为了解决结果中出现重复case的问题，如果求出具有重复case的结果，最后去重工作比较浪费时间，并且这个解决方案中多了一个模块。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    var counts = {};
    var len = nums.length;
    var res = [];
    var chain = [];
    if(len === 4){
        if(nums[0]+nums[1]+nums[2]+nums[3] === target){
            chain = nums;
            res.push(chain);
        }    
        return res;
    }
    if(len < 4){
        return res;
    }
    for(var i = 0; i<len ;i++){
        if(nums[i] in counts){
            counts[nums[i]] = counts[nums[i]] + 1;
        } else {
            counts[nums[i]] = 1;
        }
    }
    var cur = null;
    var valid = 0;
    var stack = [];
    for(var key in counts){
        // key: this nums
        // valid: nums's count
        valid = counts[key];
        if(stack.length){
            var stack_len = stack.length;
            
            for(var j = 0; j< stack_len; j++){
                for(var i = 0 ;i<=valid;i++){
                    if(stack[j] !== null){
                        cur = stack[j].concat();
                        if(i){  
                            cur[0] = cur[0] - i*key;
                            cur[1] = cur[1] + i;
                            // cur[2] = cur[2].concat(Array(i).fill(key));
                        } 
                        if(cur[0] === 0 && cur[1] === 4){
                            if(i > 1){
                                res.push(cur[2].concat(Array(i).fill(key)));
                            }
                            if(i === 1){
                                cur[2].push(key);
                                res.push(cur[2])
                            }
                            if(i === 0){
                                res.push(cur[2]);
                            }
                        } else {
                            if(stack[j][1] >= 4){
                                stack[j] = null;
                                break;
                            } else {
                                if(i>0){
                                    cur[2] = cur[2].concat(Array(i).fill(key));
                                    stack.push(cur);
                                }
                            }
                        }
                    }
                    
                }
            }
        } else {
            for(var i = 0; i<=valid; i++){
                stack.push([target-i*key,i, Array(i).fill(key)]);
            }
        }        
    }
    return res;
};

2、4指针方法
现将list排序，然后利用"i,j,left,right"四个指针，ij指针递增，left right向彼此移动
避免重复的方法是在获得一个case之后，判断left或者right和旁边的元素是否相等，如果相等，指针移动以越过相同的元素。

var fourSum = function(nums, target) {
    var res = [];
    var len = nums.length;
    if(len <= 4){
        if(len === 4 && nums[0]+nums[1]+nums[2]+nums[3] === target){
            return [nums];
        } else {
            return [];
        }
    }
    var left = null;
    var right = null;
    nums = nums.sort((a,b)=>a-b);
    for(let i = 0; i<len-3;i++){
        if(i>0 && nums[i] === nums[i-1]){continue;}
        if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target){break;}
        if(nums[i]+nums[len-1]+nums[len-2]+nums[len-3]<target){continue;}
        for(let j = i+1; j<len-2; j++){
            if(j-i>1 && nums[j] === nums[j-1]){continue;}
            if(nums[i]+nums[j]+nums[j+1]+nums[j+2] > target){break;}
            if(nums[i] + nums[j] + nums[len-1] + nums[len-2] < target){continue;}
            left = j+1;
            right = len-1;
             while(left < right){
                 let sum = nums[i]+nums[j]+nums[left]+nums[right];
                 if(sum === target){
                     res.push([nums[i],nums[j],nums[left],nums[right]]);
                     while(left < right && nums[left] === nums[left+1]){left++;}
                     while(left < right && nums[right] === nums[right-1]){right--;}
                     left++;
                     right--;
                 }
                 if(sum > target){
                     right--;
                 } 
                if(sum < target) {
                     left++;
                 }
             }

        }
    }
    return res;
};

上面两者相比仍然是指针方法用时较短。