jotting

ⓁⒸ ‧‧‧ 1. Two Sum

Posted on | Post modified | In
兩數之和

2019-07-10
更新：
增加 Golang

1. Two Sum

❀ Origin

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

❀ 翻譯

問題

給定一個整數陣列, 回傳兩個數字的指數 indices , 而這兩個數字相加必須等於目標數 target .
假設每個輸入準確地只會有一組解, 且不能回傳同個數字兩次.

❀ Solution

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  var temp = {};
  var val;
  for (var index = 0; index < nums.length; index++) {
    val = nums[index];
    // 將 target - 當前 nums[index] 的 val,
    // target 一定是兩數字的相加,
    // 所以如果 temp[target - val] >= 0 , 則代表在 temp 找得到 key
    // 且值大於或等於0 則代表找到了, 即可 return 結果陣列

    //console.log('temp', temp);
    //console.log('temp[target - val]', temp[target - val]);
    if (temp[target - val] >= 0) {
      return [temp[target - val], index];
    }

    // 找不到的話, 則將目前的 val, 當作temp的一個 key 去儲存起來,
    // 其 key 的 val 則為目前的index
    else {
      temp[val] = index;
    }
  }
};

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func twoSum(nums []int, target int) []int {
	// 使用 make 建立一個空 map , 並設置 key 和 value 的型態
	temp := make(map[int]int)
	for index, num := range nums {	
		// 取 temp[target-num] 的值（某 num 的 index），
		// 如果有值則代表在 for 迴圈的前某次，有儲存過了 target 和當下 num 的 差，
		// 意味在 temp 找得到 num 的另一半，
		// 於是可以回傳兩者的位置，則為答案。
		if value, ok := temp[target-num]; ok {
			return []int{value, index}
		}
		// 如果沒有值，
		// 則將當前的 num 作為 key; 其 index 作為 value ,
		// 存進 temp 裡，
		// 等待 range 的下一個 num 來比對。
		temp[num] = index
	}
	// func 設定了欲回傳型態，
	// 於是沒有結果的話，還是得回傳 nil
	return nil
}