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

古城微笑少年丶 2023-10-17 16:02 18阅读 0赞

算法：  
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 ($minus < 0 || $sum <= $arr[$j]) continue;
            if (isset($tmp[$minus]) && !isset($flag[$arr[$j]]) && !isset($flag[$minus])) {
                echo '数组的索引值为[' . $tmp[$arr[$j]] . ',' . $tmp[$minus] . ']<br>';
                // 如果有则将值置为1
                $flag[$arr[$j]] = 1;
            }
        }
    }
    $arr = [2, 7, 11, 15];
    //$arr = [1,2,7,9,8,3,6,5,4,10];
    twoSum($arr, 9);
     
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32

时间复杂度为O(n)。

来源:http://blog.csdn.net/fationyyk/article/details/75228347