Ruby基本介绍(五之二)-two sum解法

年轻人才做选择,我都要!

工程师会命令电脑选择甲方要的....

题目连结:https://leetcode.com/problems/two-sum/
题目说明,资料对象是一个阵列,第二参数是一个目标值,找出阵列中的两个值相加等於目标值时,回传这两个数字的位置。
整理如下

def two_sum(nums, target)
  #实作区
end

p two_sum([2, 7, 11, 15], 9) #下面会更改此例子。
p two_sum([3, 2, 4], 6)
p two_sum([3, 3], 6)

分享时会将第一个例子稍做修改,改成[11, 2, 7, 15]做分享。

解析一下这个阵列,会有以下资讯(当然是已挑出与题目有关的资讯而已)

2.7.3 :007 > nums = [11, 2, 7, 15]
 => [11, 2, 7, 15] 
2.7.3 :008 > nums.size 
 => 4 
2.7.3 :009 > nums.length
 => 4     
#虽然值一样,size与length表达的资讯还是不同,不讨论,好用会用就好。

2.7.3 :015 > nums.index(11)
 => 0 
2.7.3 :016 > nums.index(15)
 => 3 
#阵列的基本观念,第一个值位置是0,最後一个值位置是(num.size-1)。

2.7.3 :023 > for i in 0..3 do
2.7.3 :024 >     p nums[i]  #依序印出阵列各位置的值。
2.7.3 :025 > end
11
2
7
15
#for..in 回圈。

程序码通常是由上往下执行到底,回圈通常是由第一个执行依序执行到最後。

目标值:9

nuns | 11 | 2 | 7 | 15|. 这是第一层, 每一个值的位置先用一个变数代替,i.

nuns | 11 | 2 | 7 | 15|. 这是第二层, 每一个值的位置先用一个变数代替,j.

我们要下指令给电脑从第一个数字开始检查了。检查nums[i] + nums[j]是不是等於9。

nums[i]是11时(i = 0),就是依序跟第二层的2, 7, 15检查,依序是第二层的1, 2, 3位置(j)。

由於自己不会跟自己检查(11不会加11),第一层11检查後如果都没查到,也代表11不会再被检查。

那可以发现i跟j的处理顺序。

i = 0 时 j = 1. #第一层的11与第二层的2
j = i + 1

所以我们要用两个回圈来完成.....突然跳到这句会不会太快...

def two_sum(nums, target)
  for first_num in 0..(nums.size-1) do
    second_start_num = first_num + 1
      for second_num in second_start_num..(nums.size-1) do
        if nums[first_num] + nums[second_num] == target
          return [first_num, second_num]
        end
      end
  end
end

p two_sum([2, 7, 11, 15], 9) #请记得我改了第一个例子。
p two_sum([3, 2, 4], 6)
p two_sum([3, 3], 6)

def two_sum(nums, target)
  for i in 0..(nums.size-1) do
    q = i + 1
      for j in q..(nums.size-1) do
        return [i, j] if nums[i] + nums[j] == target
      end
  end
end  #自己一个月後还看得懂哪种写法就用哪种先练习...

如果不改第一个例子,会发生以下的事

def two_sum(nums, target)
  for i in 0..(nums.size-1) do
    return [i, i + 1] if nums[i] + nums[i + 1] == target
  end
end
#只看那三个例子也对

虽然在leetcode上送出会错,因为严整性不够,我在前几篇有分享,可以先从例子来想怎麽解题,但leetcode在验算时会以许多例子处理, 所以开始从leetcode刷题时,要注意的就更多了。

Hash解法

不是说接下的解法一定比较好,而是学ruby不用这解法比较可惜。
自己看不懂的东西永远不会是自己的。

def two_sum(nums, target)
  new_hash = {}
  nums.each_with_index do |num, index| 
    return [new_hash[num], index] if new_hash.has_key?(num)
    new_hash[target - num] = index
  end
end

阵列中如果有两个数字相加等於目标,那目标减去阵列中每个数字时,那两个数字会互换成对方。

nums = [2, 7, 11, 15]
new_nums = [ 9 - 2, 9 - 7, 9 - 11, 9 - 15]
new_nums = [7, 2, -2, -6]

#所以我由2开始检查时(2在阵列中的位置是0),找出有没有与2相加符合等於9的那个数字,如果有,回传2的位置及那个数字的位置给我。
#[ [2的位置] , [符合加2 = 9的那个值的位置] ]

所以我们可以直接做出一个表格来查询。

  #原nums 变成 hash , hash中 => 後面的资料是值, 但这个值刚好等於个数字在阵列的位置。
  { 2 => 0, 7 => 1, 11 =>2, 15 => 3 } 
  # 我想观察每一个数字与9相差的数字有没有在表格内。
  new_hash = { 9 - 2 => 0, 9 - 7 => 1, 9 - 11 => 2, 9 - 15 => 3 } 
  new_hash = { 7 => 0, 2 => 1, -2 => 2, -6 => 3}
  # 7请想成目标与2的关系数,关系数有没有在原本阵列里? 有的会请回报那个位置

def two_sum(nums, target)
  #我需要一个新hash
  #这个hash是由nums变来的
  #从hash中找关系值是不是在nums中
end

补充

2.7.3 :002 > new_hash = {}
2.7.3 :003 > [2, 7, 11, 15].each_with_index do |num, index| new_hash[num] = index end
 => [2, 7, 11, 15] 
2.7.3 :004 > new_hash
 => {2=>0, 7=>1, 11=>2, 15=>3} 
 
2.7.3 :007 > new_hash = {}
 => {} 
2.7.3 :008 > [2, 7, 11, 15].each_with_index do |num, index| new_hash[ 9 - num] = index end
 => [2, 7, 11, 15] 
2.7.3 :009 > new_hash
 => {7=>0, 2=>1, -2=>2, -6=>3} 
 
# 9 是 target