1. Two Sum

2020-05-20

Two Sum

原题：1. Two Sum

source code

// Runtime: 76 ms, faster than 52.22% of JavaScript online submissions for Two Sum.
// Memory Usage: 35.5 MB, less than 21.90% of JavaScript online submissions for Two Sum.

var twoSum = function(nums, target) {
    const map = {};
    for(let i = 0; i<nums.length; i++) {
        const targetIndex = map[target-nums[i]];
        if(targetIndex!==void 0) {
            return [targetIndex, i];
        }else {
            map[nums[i]] = i;
        }
    }

    //题干保证只有一个解
};

test cases:

1
2
3

test("test1", ()=>{
    expect(twoSum([2, 7, 11, 15], 9)).toEqual([0, 1]);
})

Three Sum

//这个解法一直AC不过去，但是浏览器跑超时的test case速度还行。
var threeSum = function(nums) {
    nums.sort();
    const map = nums.reduce((prev, v, i)=>{
        prev[v] = i;
        return prev;
    }, {});
    const result = {};
    for(let i = 0; i<nums.length; i++) {
        for(let j= i+1; j<nums.length; j++) {
            const targetIndex = map[0-nums[i]-nums[j]];
            if(targetIndex>j) {
                const arr = [nums[i], nums[j], nums[targetIndex]];
                result[arr.join(',')] = arr;
            }
        }
    }

    return Object.values(result);
};


//这个解法可以AC
var threeSum = function(nums) {
    const cache = {};
    for(let num of nums) {
        cache[num] = (cache[num] || 0) + 1;
    }

    let result = {};
    nums.sort((a, b)=>a-b);
    for(let i = 0; i<nums.length; i++) {
        let low = i+1;
        let high = nums.length-1;
        while(low<high) {//这里主要利用数组有序的特性，用双指针从首尾向中间逼近
            let r = nums[i] + nums[low] + nums[high];
            if(r>0) {
                high--;
            }else if(r<0){
                low++;
            }else {
                result[`${nums[i]}_${nums[low]}_${nums[high]}`] = [nums[i], nums[low], nums[high]];
                low++;
                high--;
            }
        }
    }

    return Object.values(result);
};

Four Sum

和Three Sum类似，可以基于target + Three Some的方式写出类似的解答。

var fourSum = function(nums, target) {
    const cache = {};
    for(let i = 0; i<nums.length; i++) {
        let result = threeSum(nums.slice(0, i).concat(nums.slice(i+1)), target-nums[i]);
        for(let arr of result) {
            arr = [...arr, nums[i]];
            let cacheKey = arr.sort((a,b)=>a-b).join("_");
            if(!cache[cacheKey]) {
                cache[cacheKey] = arr;
            }
        }
    }
    
    return Object.values(cache);
};