年輕人才做選擇,我都要!

工程師會命令電腦選擇甲方要的....

題目連結: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