01-两数之和

[shengxinjing]

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

评论讨论

[shengxinjing]

贴代码

[aniu2016]

var twoSum = function(nums, target) {
  let res =  {};
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    const diff = target - num;
    if (num in res) {
      return [res[num], i];
    }
    else {
      res[diff] = i;
    }
  }
};

[zqqhyy]

let twoSum = function(nums, target) {
   for (let i = 0; i < nums.length; i++){
        let needNum = target - nums[i];
        // 从后面剩余的元素中找
        let result = nums.slice(i+1).indexOf(needNum);
        if (result !== -1) {
            return [i, result+(i+1)]
        }
    }
};

这种也是遍历了一次，但是执行用时是190ms左右，内存消耗是40MB,是因为操作了数组么，数组和对象不都是引用类型，为啥数组操作这么耗时捏 数组：192 ms | 41.1 MB 对象：60ms | 35.2MB

[kaizige10]

var twoSum = function (nums, target) {
    const need = new Map()
    for (let i = 0; i < nums.length; i++) {
        if (need.has(target - nums[i])) {
            return [need.get(target - nums[i]), i]
        } else {
            need.set(nums[i], i)
        }
    }
};

用Map测了几次，最快56ms，最慢100ms，不知道为啥

[shengxinjing]

@aniu2016 @zqqhyy @kaizige10 可以思考下3数之和

[chenbingweb]

var twoSum = function(nums, target) { let arr=[]; for(let i=0;i<nums.length;i++){ let dif = target-nums[i] if(arr[dif]!==undefined) { return [arr[dif],i] } else { arr[nums[i]]=i; } } }; 执行用时 :76 ms,

[kaizige10]

@aniu2016 @zqqhyy @kaizige10 可以思考下3数之和

我用如下做法拿去提交，结果超时了:cry:

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    let results = []
    for (let i = 0; i < nums.length; i++) {
        let needMap = new Map()
        for (let j = i + 1; j < nums.length; j++) {
            const need = 0 - nums[i] - nums[j]
            if (needMap.has(need)) {
                // 判断是否重复
                if (!results.find(result => {
                    return isSame(result, [nums[i], nums[j], need])
                })) {
                    results.push([nums[i], nums[j], need])
                }
            } else {
                needMap.set(nums[j], 1)
            }
        }
    }
    return results
};

function isSame(a1, a2) {
    for (let i = 0; i < a1.length; i++) {
        let j = a2.indexOf(a1[i])
        if (j===-1) return false
        a2.splice(j, 1)
    }
    return true
}

我最初的想法是参考TwoSum的解法，用优化的双重循环，然后对重复的项做过滤。 我后来看了leetcode的题解，大家的做法是排序+双指针，时间复杂度其实也是O(n^2)，但是我这个就不行。 我想主要原因是我的判重也是做了一次循环，时间复杂度太高了。

[kaizige10]

三数之和按照最高票题解思路，我的答案：

/**
 * threeSum 思路是排序后，通过固定第一个数，双指针遍历找到所有解
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    // 先排序
    nums.sort((a,b)=>a-b)
    
    let result = []
    for (let i = 0; i < nums.length;) {
        let left = i + 1, right = nums.length - 1
        while(left < right) {
            let sum = nums[i] + nums[left] + nums[right];
            // 满足条件
            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]])
                // 过滤掉相同的项目
                while(nums[left] === nums[++left]) {}
                while(nums[right] === nums[--right]) {}
            }
            // 不满足且小于0，较小者增大
            if (sum < 0) {
                left++
            }
            // 不满足且小于0，较大者减小
            if (sum > 0) {
                right--
            }
        }
        // 重复的num[i]跳过
        while(nums[i] === nums[++i]) {}
    }
    return result
};

[yuzhou1990]

let twoSum = function(nums, target) {
   for (let i = 0; i < nums.length; i++){
        let needNum = target - nums[i];
        // 从后面剩余的元素中找
        let result = nums.slice(i+1).indexOf(needNum);
        if (result !== -1) {
            return [i, result+(i+1)]
        }
    }
};

这种也是遍历了一次，但是执行用时是190ms左右，内存消耗是40MB,是因为操作了数组么，数组和对象不都是引用类型，为啥数组操作这么耗时捏 数组：192 ms | 41.1 MB 对象：60ms | 35.2MB

我的分析：1.每次都是从剩余的数组里面查找目标，会增加时间 2.slice会返回新的数组，会增加空间

[kouchao]

var twoSum = function(nums, target) {

    const map = {};
    for(let i = 0; i < nums.length; i++){
        if(map[nums[i]] >= 0){
            return [map[nums[i]] , i]
        }
        map[target - nums[i]] = i
    }
};

[TimCN]

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let obj = {};
  let coNums;
  for (let i = 0; i < nums.length; i++) {
    coNums = target - nums[i]
    if (coNums in obj) {
      return [obj[coNums], i]

    }
    obj[nums[i]] = i
  }
};