Go 和 PHP 根据目标值计算两数之和

Go 和 PHP 根据目标值计算两数之和

author: he xiaodong date: 2020-04-16

原文链接:go leetcode,php 代码个人原创

两数之和(Two Sum)

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。 示例:     给定 nums = [2, 7, 11, 15],target = 9     因为 nums[0] + nums[1] = 2 + 7 = 9     所以返回 [0, 1] 来源:力扣

简单来说就是给定一个数组,让你找到和为 target 的两个元素的索引。

解题思路

主要有 两种解题思路

  • 暴力解法:两层循环,外部循环的当前值与target的差值为内层循环需要定位的值。时间复杂度O(n^2),空间复杂度O(1)。
  • 优雅解法:一层循环,引入map,循环的当前值与target的差值在map中查找,如果不存在则将当前值作为键放入map,值的索引作为map的值,存在就返回。时间复杂度O(n),空间复杂度O(n)。相比于暴力解法其实就是空间换时间。

Go 实现

/*优雅解法
思路:
	一层循环,引入map,循环的当前值与target的差值在map中查找,如果不存在则将当前值作为键放入map,值的索引作为map的值。
*/
func twoSumElegant(nums []int, target int) (result []int) {
	if len(nums) <= 0 {
		return
	}
	var m = make(map[int]int)
	for index, value := range nums {
		if v, ok := m[target-value]; !ok {
			// 将当前值和索引放入map中
			m[value] = index
		} else {
			return []int{index,v}
		}
	}
	return

}

func main() {
	var (
		nums   = []int{2, 7, 11, 15}
		target = 10
	)

	fmt.Println(twoSumElegant(nums, target))
}

PHP 实现

function twoSum($nums, $target) {
    $count = count($nums);
    if ($count <= 0) {
        return '';
	}

    $tmp = [];  // 中间交换数组
    for ($i = 0; $i < $count; $i++) {
		reset($tmp);
		$firstKey = key($tmp);
        // 如果当前值不等于目标值减第一个key的值,则将 $tmp 数组的内容置换为当前值和key
        if ($nums[$i] !== $target - $firstKey) {
            $tmp = [];
            $tmp[$nums[$i]] = $i;
        } else {
            // 如果匹配,根据 $tmp 当前键的值返回所属 key 和 当前 $i
            return [$tmp[firstKey], $i];
        }
    }

	return [];
}

return twoSum([1,7,8,5,6], 18); // output: []
return twoSum([1,7,8,5,6], 15); // output: [1,2]

PHP 实现2 来自 laravel china 社区 幽弥狂

function twoSum($nums, $target) {
	$data = [];
	foreach($nums as $key => $val) {
		$data[$val] = $key;
	}

	foreach($nums as $k => $v) {
		$dataKey = $target - $v;
		if (isset($data[$dataKey]) && $k !== $data[$dataKey]) {
			return [$k, $data[$dataKey]];
		}
	}

	return [];
}

return twoSum([1,7,8,5,6], 18); // output: []
return twoSum([1,7,8,5,6], 15); // output: [1,2]