1.两数之和.md

1.两数之和

url

题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

输入：nums = [3,2,4], target = 6
输出：[1,2]

方法

哈希映射

1. 可以用中间空间来协调或者帮助，采用哈希是因为比较快，为啥呢？输入的x元素通过哈希函数将其映射到某个位置上，那岂不是非常快？顶多通过计算就知道x的位置了。
2. 采用哈希呢，你正好key对应x，value对应的是索引i
3. 核心过程：每遍历一次就要做一些事情
   1. 算一下x与target的差为sub
   2. 我哈希空间是否存在sub，
   3. 存在的话，返回x的索引i和sub对应的value，即i。
   4. 不存在，那好办，我将x设置为key，其索引i存value，放到该哈希空间内，目的是方便下一次遍历的sub是否能找的到，如果找的到，那岂不是x+sub=target？ 两数之和？

code

js

let twoSum = function(nums, target) {
    let m = new Map();
    for (let i = 0; i < nums.length; i++) { // 遍历
        const sub = target - nums[i]
        if (m.has(sub)) {
            return [m.get(sub), i];
        } else {
            m.set(nums[i], i);
        }
    }
    return [];
}
console.log(twoSum([2, 7, 11, 15], 9))

go

func twoSum(nums []int, target int) []int {
	// 创建map
	m := make(map[int]int, len(nums))
	// 遍历元素和目标值的差是否在该map内
	for i, v := range nums {
		sub := target - v  // 当前元素和目标值的差
		if j, ok := m[sub]; ok {
			return []int{j, i};
		} else {
			m[v] = i // 差若是不在当前map内，则存到map
		}
	}
	return nil
}
func main() {
	nums := []int{2, 7, 11, 15}
	target := 9
	fmt.Println(twoSum(nums, target))
}

java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) return null;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int sub = target - nums[i];
            if (map.containsKey(sub)) {
                return new int[] {map.get(sub), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[0];
    }
}