共计 1041 个字符,预计需要花费 3 分钟才能阅读完成。
题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标
你能够假如每种输出只会对应一个答案。然而,数组中同一个元素不能应用两遍
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
办法一:暴力解法
思路:
将数组中的所有可能的两两组合进行相加,而后和指标数字比拟,如果相等,那么这两个元素所对应的下标就是咱们想要的后果。置信聪慧的你曾经想到通过双层 for 循环来解决
class LeetCode0001
{public function twoSum($nums, $target)
{$len = count($nums);
for($i = 0; $i< $len; $i++) {for ($j=$i+1; $j<$len;$j++) {if ($nums[$i] + $nums[$j] == $target) {return [$i, $j];
}
}
}
}
}
工夫复杂度为:O(n^2)
空间复杂度:O(1)
办法二:数组翻转
思路:
A + B = target
A 和 B 是数组中的元素,targer 为目标值
换种思路,既然数组中两个元素的和为指标数,也就是说
- 拿目标值 targer 减去一个数组中的元素 A /B,失去的值 A /B,也肯定是在数组中的一个元素
- 这种形式能够不便的找到这两个值,问题是,题目要求拿到对应的值的下标
- 那如果,每当我拿指标数 target 减数组中的一个元素 A / B 时,都把这个 被减的元素 A /B,当作 下标 放入到一个新的数组中,将 该元素的下标当作新数组对应的值
- 此时就能够奇妙的利用 php 中的 array_key_exists 函数,判断目标值 target 减 A / B 的后果是否是新数组中的某一个元素的下标,则这个下标对应的值,就是咱们要找的原数组中该元素对应的下标
形容有点形象,代码一看就明确,间接上代码
class LeetCode0001{public function twoSume2($nums, $target)
{$len = count($nums);
$flip = [];
for ($i=0; $i<$len; $i++) {$findValue = $target-$nums[$i];
if (array_key_exists($findValue, $flip)) {return [$flip[$findValue], $i];
}
$flip[$nums[$i]] = $i;
}
}
}
工夫复杂度:O(n)
空间复杂度:O(n)
拿空间换工夫的一种做法
正文完