每日一题——两数之和

题目描述

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

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

示例:

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

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

思路

• 暴力枚举，利用两层 for 循环来遍历每个元素，并查找满足条件的目标元素。时间复杂度为 O(N^2)，空间复杂度为 O(1)
• 通过添加一个 Map 记录遍历过的数字及其对应的索引，这样当遍历一个新数字的时候去 Map 里查询，target 与该数的差值是否已经在前面的数字中出现过。如果出现过，那么已经得出答案，就不必再往下执行了。时间复杂度 O(n)，空间复杂度 O(n)。

代码

PHP：

/**
 * 方法一：暴力枚举，两次循环
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer[]
 */
function twoSum($nums, $target) {
    foreach($nums as $key => $value) {
        foreach($nums as $k => $v) {
            if ($v == $value)
                continue;
            if ($target == $v + $value) {
                return [$key, $k];
            }
        }
    }
}

/**
 * 方法二：通过中间 Map 记录遍历过的数字及其对应的索引
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer[]
 */
function twoSum($nums, $target) {
	$map = [];
    for ($i = 0; $i < count($nums); $i++) {
        $sub = $target - $nums[$i];
        if (in_array($sub, $map)) {
            $key = array_keys($map, $sub);
            return [$key[0], $i];
        }
        $map[$i] = $nums[$i];
    }
}

Golang：

// 方法一：暴力枚举，两次循环
func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
		for j := i+1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				return []int{i, j}
			}
		}
	}
	return nil
}

// 方法二：通过中间 Map 记录遍历过的数字及其对应的索引
func twoSum(nums []int, target int) []int {
    m := map[int]int{}
	for i, v := range nums {
		if k, ok := m[target-v]; ok {
			return []int{k, i}
		}
		m[v] = i
	}
	return nil
}