sisterAn/JavaScript-Algorithms

字节&leetcode1：两数之和

sisterAn opened this issue · 22 comments

sisterAn commented

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

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

示例:

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

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

附leetcode地址：leetcode

可结合 腾讯&leetcode15：三数之和 一起查看

JerryWen1994 commented 
let nums = [2, 7, 11, 15],
      target = 26;

    function getSumIndex(arr1, sum) {
      let i = 0;
      while (i < arr1.length) {
        const j = arr1.slice(i + 1).findIndex(item => arr1[i] + item === sum);
        if (j !== -1) {
          console.log([i, i + 1 + j]);
          return [i, i + 1 + j];
        } else {
          i++;
        }
      }
      console.log("[]");
      return [];
    }

    getSumIndex(nums, target);
  • 👍1
  • 👎12
sisterAn commented

解题思路：

  • 初始化一个 map = new Map()
  • 从第一个元素开始遍历 nums
  • 获取目标值与 nums[i] 的差值，即 k = target - nums[i] ，判断差值在 map 中是否存在
    • 不存在（ map.has(k) 为 false ） ，则将 nums[i] 加入到 map 中（key为nums[i], value为 i ，方便查找map中是否存在某值，并可以通过 get 方法直接拿到下标）
    • 存在（ map.has(k) ），返回 [map.get(k), i] ，求解结束
  • 遍历结束，则 nums 中没有符合条件的两个数，返回 []

时间复杂度：O(n)

代码实现：

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

leetcode

  • 👍41
  • 👎1
  • 🎉4
  • 🚀4
liwuhou commented 
function findSumIdx(arr, target){
    let num1 = null, num2 = null;
    for(let i=0; i<arr.length; i++){
        for(let j=i; j<arr.length-i; j++){
            if(arr[i] + arr[j] ===target){
                num1 = i,num2 = j;
                break;
            }
        }
        if(num1 && num2) break;
    }
    return [num1, num2];
}
  • 👎6
uuRRx0 commented 
//不考虑数组含有负数
function findIndex(arr, target) {
    var len = arr.length;
    for(var i = 0; i < len; i++){
        if(arr[i] > target) continue;
        for(var j = i + 1; j < len; j++) {
            if (arr[j] > target) continue;
            if(target === arr[i] + arr[j]) return [i,j];
        } 
    }
}
  • 👎4
Aiyoweioo commented

用一个hash来检查是否已经存在过该元素，用一次循环。要返回的是数组下标的索引

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  var map = {}
  for(var i = 0; i < nums.length;i++){
    if(map.hasOwnProperty(target-nums[i])){ // 边循环边检查，有就直接返回
      return [map[target-nums[i]], i]
    }else{ // 没有就添加到哈希表里头
      map[nums[i]] = i // key为值，下标为索引
    }
  }
};
pb1314you commented

function getTargetFromArray(nums, target){
let findIndex = [];
nums.map((num,i)=>{
let anotherNum = target-num;
let _findIndex = nums.findIndex(item =>item === anotherNum)
if(_findIndex>-1 && _findIndex!=i&&findIndex.length==0){
findIndex = [i, _findIndex]
}
})
return findIndex;
}

lyy199212 commented

let getSumIndex = ()=>{
for (let index = 0; index < nums.length; index++) {
const element = nums[index];
let newArr = nums;
newArr[index] = '';//随便写个值占位
if(nums.indexOf(target-element)>-1){
return [index,nums.indexOf(target-element)]
}
}
}

chenjingtian commented 
function getNumber(arr, target) {
  for (let i = 0; i < arr.length - 1; i++) {
    const midNumber = target / 2
    for (let j = i + 1; j < arr.length; j++) {
      let one = arr[i] - midNumber
      let another = arr[j] - midNumber
      if (
        Math.abs(one) == Math.abs(another) &&
        ((one >= 0 && another <= 0) || (one <= 0 && another >= 0))
      ) {
        return [i, j]
      }
    }
  }
}
let arr = [4, 1, 0.5, 4]
let target = 2
console.log('结果', getNumber(arr, target))
babybrotherzb commented 
var twoSum = function(nums, target) {
    let len = nums.length
    for(let i=0;i<len;i++){
       if(nums.lastIndexOf(target-nums[i])!==-1&&nums.lastIndexOf(target-nums[i])!==i){
           return [i,nums.lastIndexOf(target-nums[i])]
       }
    }
};
var twoSum = function(nums, target) {
   let len = nums.length
      let obj = {}
      let cha
      for(let i=0;i<len;i++){
          cha = target - nums[i]
         if(obj[cha]!==undefined){
             return [obj[cha],i]
         }
          obj[nums[i]] = i
      }
};
guanping1210 commented

思路：
1、循环遍历一次，用目标值减去当前下标的值，得出一个减数值
2、判断这个减数值，是否存在，不存在或者是当前下标的值，则退出当前循环，进行下一次循环

    const getTargeSumIndex = (arr, sum) => {
            for(let i = 0; i < arr.length; i ++) {
                const reduce = sum - arr[i]
                const reduceIndex = arr.indexOf(reduce)
                //  reduce不存在或者 reduce的下标等于当前下标，退出
                if(reduceIndex === -1 || reduceIndex === i) {
                    continue
                }
               // 找到满足的数据，break 退出循环
                return [i, reduceIndex]
                break
            }

            return []
        }
BertieGo commented 
const sum = (arr, target) => {
            let result = [];
            arr.some((num, index) => {
                const i = arr.findIndex(n => n !== num && n + num === target);
                const found = i >= 0;
                if (found) {
                    result = [].concat([i, index])
                }
                return found;
            })
            return result;
        }
  • 👍1
scottdao commented

function(nums, target){
let cache = {};
for(let i = 0, len = nums.length; i<len; i++){
let ele = target - nums[i];
if(cache[ele] !== undefined){
return [cache[ele], i]
}
cache[nums[i]] = i;
}

}

  • 👍1
xingorg1 commented

解题思路：

  • 初始化一个 map = new Map()

  • 从第一个元素开始遍历 nums

  • 获取目标值与 nums[i] 的差值，即 k = target - nums[i] ，判断差值在 map 中是否存在

    • 不存在（ map.has(k) 为 false ） ，则将 nums[i] 加入到 map 中（key为nums[i], value为 i ，方便查找map中是否存在某值，并可以通过 get 方法直接拿到下标）
    • 存在（ map.has(k) ），返回 [map.get(k), i] ，求解结束

  • 遍历结束，则 nums 中没有符合条件的两个数，返回 []

时间复杂度：O(n)

代码实现：

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

leetcode

请问用map实现和用纯对象实现，对比来说map实现会有什么优势吗

2456844450 commented

the time complexity of map calling method is O(1), so using map makes the total time complexity very small.

Been101 commented 
// 正整数数组，可以使用 {} 来存储数据
var twoSum = function(nums, target) {
    let map = {}
    for(let i = 0; i< nums.length; i++) {
        let k = target-nums[i]
        if(map[k]) {
            return [map[k, i]
        }
        map[nums[i]] = i
    }
    return [];
};
AnranS commented 
var twoSum = function(nums, target) {
    let tmpMap = new Map();
    for(let index = 0;index < nums.length; index ++) {
        let toSearch = target - nums[index];
        if(tmpMap.has(toSearch)) {
            return [tmpMap.get(toSearch), index]
        }
        tmpMap.set(nums[index], index);
    }
};
Eason-Wu commented 
var twoSum2 =  function( nums, target) {
    for(let i =0,len = nums.length; i< len; i++) {
        let diff = target - nums[i];
        let pos = nums.lastIndexOf(diff);
        if (pos > i) return [i, pos];
    }

    return [];
}
azl397985856 commented

题目地址(1. 两数之和)

https://leetcode-cn.com/problems/two-sum

题目描述

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

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

示例:

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

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

前置知识

  • 哈希表

公司

  • 字节
  • 百度
  • 腾讯
  • adobe
  • airbnb
  • amazon
  • apple
  • bloomberg
  • dropbox
  • facebook
  • linkedin
  • microsoft
  • uber
  • yahoo
  • yelp

思路

最容易想到的就是暴力枚举，我们可以利用两层 for 循环来遍历每个元素，并查找满足条件的目标元素。不过这样时间复杂度为 O(N^2)，空间复杂度为 O(1)，时间复杂度较高，我们要想办法进行优化。

这里我们可以增加一个 Map 记录已经遍历过的数字及其对应的索引值。这样当遍历一个新数字的时候就去 Map 里查询 target 与该数的差值是否已经在前面的数字中出现过。如果出现过，就找到了答案，就不必再往下继续执行了。

关键点

  • 求和转换为求差
  • 借助 Map 结构将数组中每个元素及其索引相互对应
  • 以空间换时间，将查找时间从 O(N) 降低到 O(1)

代码

  • 语言支持：JS, Go，CPP
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function (nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    map.set(nums[i], i);
  }
};

Go Code:

func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i, _ := range nums {
		diff := target - nums[i]
		if j, ok := m[diff]; ok {
			return []int{i, j}
		} else {
			m[nums[i]] = i
		}
	}
	return []int{}
}

CPP Code:

class Solution {
public:
    vector<int> twoSum(vector<int>& A, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < A.size(); ++i) {
            int t = target - A[i];
            if (m.count(t)) return { m[t], i };
            m[A[i]] = i;
        }
        return {};
    }
};

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

  • 👍1
oakland commented

@sisterAn 请教下 hash 为什么用 Map，而不用 Object 呢？

painting-alt commented 
var twoSum = function(nums, target) {
    let newArr = []
      for(let i = 0; i < nums.length; i++){
        for(let j = i + 1; j < nums.length; j++){
          if(nums[i] + nums[j] == target){
            newArr.push(i)
            newArr.push(j)
            break
          }
        }
      }
      return newArr
};
XW666 commented 
 function twoSum(nums, target) {
    let map = {}
    let arr = []
    arr.forEach((item, index) => {
      map[item] = index
    })
    for (let i = 0; i < nums.length; i++) {
      let v = target - nums[i]

      if (map[v]) {
        arr = [i, map[v]]
        break
      }
    }
    return arr
  }
tianshiyang commented

function sum(arr, target) {
let i = 0,
k = arr.length - 1
while (i < k) {
if (arr[i] + arr[k] > target) {
k --
} else if (arr[i] + arr[k] < target) {
i ++
} else {
return [i, k]
}
}
return false
}