(leetcode) 1. 两数之和



  • 来自: 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]
    


  • 其实题目讲的不是很清楚, 比如数据规模, 以及整数范围. 以及"数组中同一个元素不能使用两遍", 我误以为不可重复. 以下解法是当成不可重复的来实现的, 好在我们关注的练习, 而不是非得解题

    A. 假如数据规模不是很大, 并且是正整数的话, 那么可以用数组来存储位置, 比如示例中, num = [2,7,11,15] 就可以转化成num[2]=1, num[7]=2,num[11]=3,num[15]=4 我们假定偏移从1开始, 如果是0, 则表示不存在对应值.

    步骤如下:

    1. 从数组num中找出最大值
    2. 根据最大值分配数组T
    3. 循环数组num,设置T对应位置的偏移(注: 从1开始, 因为0被用来表示不存在)
    4. 再循环数组num, 得到 [target - 当前元素] 对应的偏移位置, 便是了...
      大致是3次遍历num, 即, O(3n)
    //
    // PHP代码如下
    // 我感觉PHP做为一种宏语言来描述算法也不错
    //
    
    function twoSum($nums, $target) {
      $maps = array_flip($nums);
      $rests = array_map(function($item) use($target) { return $target - $item; }, $nums);
      // leetcode 里php版本不是最新的 不然 fn($item) => $target - $item 
      // 自然是最好的
      
      $ret = [];
      foreach($rests as $k => $v) {
        if (isset($maps[$v]) && ($v<<1 !== $target)) {
          $ret[$k] = true;
        }
      }
    
      return array_keys($ret);
    }
    

Log in to reply