2020-04-16-Go和PHP根据目标值计算两数之和

layout: posttitle: Go 和 PHP 根据目标值计算两数之和
subtitle: Go 和 PHP 根据目标值计算两数之和
date: 2020-04-16
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 两数相加

原文链接：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]

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券