1. 两数之和

码农天地 - 2020-10-14 06:18:40

1.暴力双循环略过不提；
2.哈希表(桶);
对于数组A，构造一个哈希，初次遍历时候就记录下值和数组下标，再遍历过程中，先判断哈希表里是否已经有target - A[i]，有的话，直接返回就好了;

复杂度分析
时间复杂度：O(N)，其中 N是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $len = count($nums);
        $table = [];
        $result = [];
        //php数组的底层实现就是hash表，这里就不像c一样计算最小值那些了步骤了，直接一把梭
        for($i=0;$i < $len;$i++) {
            //先判断是否有，有的话直接返回下标
            if (isset($table[$target - $nums[$i]])) {
                return [$table[$target - $nums[$i]],$i];
            }else{
            //否则hash里的数字 => 下标
                $table[$nums[$i]] = $i;
            }
        }
    }
}

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。