其实题目讲的不是很清楚, 比如数据规模, 以及整数范围. 以及"数组中同一个元素不能使用两遍", 我误以为不可重复. 以下解法是当成不可重复的来实现的, 好在我们关注的练习, 而不是非得解题。
A. 假如数据规模不是很大, 并且是正整数的话, 那么可以用数组来存储位置, 比如示例中, num = [2,7,11,15] 就可以转化成num[2]=1, num[7]=2,num[11]=3,num[15]=4 我们假定偏移从1开始, 如果是0, 则表示不存在对应值.
步骤如下:
从数组num中找出最大值
根据最大值分配数组T
循环数组num，设置T对应位置的偏移(注: 从1开始, 因为0被用来表示不存在)
再循环数组num, 得到 [target - 当前元素] 对应的偏移位置, 便是了...
大致是3次遍历num, 即, O(3n)
//
// PHP代码如下
// 我感觉PHP做为一种宏语言来描述算法也不错
//
function twoSum($nums, $target) {
$maps = array_flip($nums);
$rests = array_map(function($item) use($target) { return $target - $item; }, $nums);
// leetcode 里php版本不是最新的 不然 fn($item) => $target - $item
// 自然是最好的
$ret = [];
foreach($rests as $k => $v) {
if (isset($maps[$v]) && ($v<<1 !== $target)) {
$ret[$k] = true;
}
}
return array_keys($ret);
}