52XUE Logo

好好学习,天天向上



LeetCode刷题(1):两数之和

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]


题解:

       拿到题目以后很自然想到循环数组,然后用目标数减去当前循环的数得到差值,再去循环判断插值是否在剩下的数组中,两个循环所以复杂度为n^2,这显然不可行,考虑到关键点就在于怎么判断差值是否在数组中,我们只需要拿到下标即可,那么我们可以将key和value位置互换,多个相同的数字下标作为子数组存储,如下:

执行用时 12 ms

内存消耗 20.4 MB

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $maps = [];
        foreach($nums as $i => $num){
            $maps[$num][] = $i;
        }
        foreach ($nums as $i => $num) {
            if (isset($maps[$target - $num])) {
                if (count($maps[$target - $num]) == 1) {
                    if ($i !== $maps[$target - $num][0]) {
                        return [$i, $maps[$target - $num][0]];
                    }        
                }else{
                    return [$i, $maps[$target - $num][1]];
                }
            }
        }
        
        return [];
    }
}


看其他大神的解答才想起来有个array_flip函数可用,array_flip可以覆盖前面的键,所以可以更精简,如下:

执行用时 12 ms

内存消耗 16.8 MB

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $maps = array_flip($nums);
        foreach ($nums as $i => $num) {
            if (isset($maps[$target - $num]) && $maps[$target - $num] !== $i) {
                return [$i, $maps[$target - $num]];
            }
        }
        
        return [];
    }
}

作者:wuzhh

链接:https://leetcode-cn.com/problems/two-sum/solution/xian-chou-liao-phpjie-fa-by-wuzhh/

来源:力扣(LeetCode)

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



作者  :  超人会飞吗

天上地久有时尽,此恨绵绵无绝期。




about me

剪一束月光

秋风清,秋月明。
落叶聚还散,
寒鸦栖复惊。
相思相见知何日,
此时此夜难为情。

联系站长

热门标签