(leetcode) 1. 两数之和

yarco

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

yarco

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

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

步骤如下:

从数组num中找出最大值
根据最大值分配数组T
循环数组num，设置T对应位置的偏移(注: 从1开始, 因为0被用来表示不存在)
再循环数组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);
}