PHP实现数组中两个数的和等于给定的目标值

算法：
1、以数组中的值为索引创建新的数组$tmp
2、求出目标值减去数组值得差值
3、判断该差值是否在$tmp中。
php实现代码如下

/**
 * Given an array of integers, return indices of the two numbers such that they add up to a specific target.
 * You may assume that each input would have exactly one solution, and you may not use the same 
 * element twice.
 * Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
 * @param  [type] $arr [description]
 * @param  [type] $sum [description]
 * @return [type]      [description]
 */
function twoSum($arr, $sum) {
    $len = count($arr);
    if ($len < 2) return false;
    $tmp = [];
    $flag = [];
    // 以数组的值为索引
    for ($i = 0; $i < $len; $i++) {
        $tmp[$arr[$i]] = $i;
    }
    // 判断差值是否在上述索引数组中
    for ($j = 0; $j < $len; $j++) {
        $minus = $sum - $arr[$j];
        /*
        if (isset($tmp[$minus]) && !isset($flag[$arr[$j]]) && !isset($flag[$minus])) {
            echo "数组的索引值为[" . $tmp[$arr[$j]] . "," . $tmp[$minus] . "]<br>";
            // 如果有则将值置为1
            $flag[$arr[$j]] = 1;
        }*/
        if (isset($tmp[$minus])) {
            $flag[] = $minus;
        }
    }
    return $flag;
}
$arr = [2, 7, 11, 15];
//$arr = [1,2,7,9,8,3,6,5,4,10];
twoSum($arr, 9);

时间复杂度为O(n)。