字节&leetcode1：两数之和

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

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

示例:

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

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

附leetcode地址：leetcode

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

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);

解题思路：

初始化一个 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

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];
}

//不考虑数组含有负数
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];
        } 
    }
}

用一个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为值，下标为索引
    }
  }
};

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))

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
      }
};

思路：
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 []
        }

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;
        }

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;
}

}

解题思路：

初始化一个 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实现会有什么优势吗

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

// 正整数数组，可以使用 {} 来存储数据
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 [];
};

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);
    }
};

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 [];
}

题目地址(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 啦。

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

@sisterAn

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

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
};

 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
  }

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
}

Navigation Menu

Repository navigation

字节&leetcode1：两数之和 #4

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

题目描述

前置知识

公司

思路

关键点

代码

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

字节&leetcode1：两数之和 #4

Description

Activity

JerryWen1994 commented on Apr 3, 2020

sisterAn commented on Apr 4, 2020

liwuhou commented on Apr 6, 2020

uuRRx0 commented on Apr 6, 2020

Aiyoweioo commented on Apr 26, 2020

pb1314you commented on Apr 29, 2020

lyy199212 commented on May 13, 2020

chenjingtian commented on May 15, 2020

babybrotherzb commented on May 22, 2020

guanping1210 commented on May 26, 2020

BertieGo commented on Jun 13, 2020

scottdao commented on Jun 23, 2020

xingorg1 commented on Jun 23, 2020

2456844450 commented on Jun 27, 2020

Been101 commented on Jul 11, 2020

AnranS commented on Nov 16, 2020

Eason-Wu commented on Jan 27, 2021

azl397985856 commented on Mar 3, 2021

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

题目描述

前置知识

公司

思路

关键点

代码

oakland commented on Apr 28, 2021

painting-alt commented on Oct 8, 2021

XW666 commented on Feb 9, 2022

tianshiyang commented on Jan 15, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions