01-算法练习：求两数之和（php实现）

题目来源：https://leetcode-cn.com/problems/two-sum/

题目：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法一：枚举（v1）

function twoSum($nums, $target) {
    $result = [];
    foreach ($nums as $_k1 => $_v1) {
        foreach ($nums as $_k2 => $_v2) {
            if ($_k1 == $_k2) {
                continue;
            }
            if (($_v1 + $_v2) == $target) {
                $result = [$_k1, $_k2];
                break 2;
            }
        }
    }
    return $result;
}

$nums = [2, 7, 11, 15];
$target = 9;
$res = twoSum($nums, $target);
print_r($res);

这个解法应该是大多数人最先想到的方法，也是最笨的方法，方法虽然简单，但是有些细节需要注意一下，不然覆盖不到所有测试用例，会出现bug，

• nums中可能会包含负数
  • 刚开始的时候我没有考虑到负数，为了减少匹配次数，加了类似与$value <= $target的逻辑，导致包含负数的测试用例无法通过；
• 同一个位置的数不能重复使用
• 只需要返回一个结果就可以，找到结果时及时跳出循环

测试结果：

执行用时: 2492 ms, 在Two Sum的PHP提交中击败了19% 的用户

2. 解法二：两次遍历（v2）

function twoSum($nums, $target) {
    $result = [];
    $nums_match = [];
    foreach ($nums as $_k => $_v) {
        if (!isset($nums_match[$target - $_v])) {
            $nums_match[$target - $_v] = $_k;
        }
    }

    foreach ($nums as $_k => $_v) {
        if (isset($nums_match[$_v]) && $nums_match[$_v] != $_k) {
            $result = [
                $_k,
                $nums_match[$_v],
            ];
            break;
        }
    }

    return $result;
}

这个解法花费了一番心思，主要的解题思路是想办法把两层循环改成一层循环来解决，降低程序执行的时间复杂度。

第一次循环是通过关联数组（hash表）的方式记录target - value和key的对应关系，第二次循环的目的是找出第一次循环中记录的target - value的值，如果能找到，证明存在value + (target - value) = target的匹配对，及时返回结果即可。

尝试本次解法的过程中踩过的几个坑：

• nums中的两个数可能重复，所以要及时判断hash表中的key是否已经存在。
• 返回值的顺序需要考虑。

测试结果：

执行用时: 24 ms, 在Two Sum的PHP提交中击败了97.26% 的用户

解法三：一次遍历（v3）

function twoSum($nums, $target) {
    $result = [];
    $nums_match = [];
    foreach ($nums as $_k => $_v) {
        if (!isset($nums_match[$target - $_v])) {
            $nums_match[$target - $_v] = $_k;
        }

        if (isset($nums_match[$_v]) && $nums_match[$_v] != $_k) {
            $result = [
                $_k,
                $nums_match[$_v],
            ];
            break;
        }
    }

    return $result;
}

这个解法是在解法二的基础上改进而来的，可以看到解法二中对nums数组做了两次遍历，所以这里两次两次遍历合并成一次遍历，就是解法三。

这个解法不是我自己想出来的，完成解法二后看了一下官方给出的解法，官方一共给了三种解法，前两种解法跟我的解法一致，第三种是对解法二的优化。

测试结果：

执行用时: 20 ms, 在Two Sum的PHP提交中击败了100% 的用户