原文链接：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]
最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券
