Image From LeetCodeImage From LeetCode

今天我們要講解的是 [Two Sum],這在 LeetCode 算是比較簡單的題目,讓我們一起開始吧!

進來之前請先注意,我的方式不一定完全正確,只是依照我自己的理念進行撰寫,所以如果程式上有什麼更好的解法,歡迎提出見解。

這次題目

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].

自己解法

預期一開始原本想說用兩層 For 迴圈去解,雖然能確實解出來,但問題在效能上卻掉了好幾個百分比,複雜度 O(n),當內容越多也代表要處理的時間越久,所以我透過鍵值的方式去確認值是否存在,如下:

初始他會給你預設值,要你在下方的twoSum進行處理接著回傳回去。

1
2
3
4
5
6
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {};

初步我們建立陣列,用來放置參數值,依照題目參考的nums會依照結果來命名 key 值,接著建立回傳的數值,記得設定let讓他可被更改。

1
2
3
4
5
6
7
8
9
10
11
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
// 紀錄已被拿出過得值
const mapNumber = {};
// 最終回傳得值
let mapCount = [];
};

接著我們透過For迴圈來比對資料,並且把目前選擇的內容丟到num的參數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
// 紀錄已被拿出過得值
const mapNumber = {};
// 最終回傳得值
let mapCount = [];
for (let i = 0; i < nums.length; i++) {
// 當前的值
let num = nums[i];
}
};

接著我們取得需要的值,就完成,說明如下:

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
29
30
31
32
33
34
35
36
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
// 紀錄已被拿出過得值
const mapNumber = {};
// 最終回傳得值
let mapCount = [];
for (let i = 0; i < nums.length; i++) {
// 當前的值
let num = nums[i];

/**
* x + y = ans
* 所以 => y = ans - x
* 範例
* => 2 + y = 9
* => y = 9 - 2
* 測試就會如下方則的targetNum
*
* 另外有個小問題,因為產生的物件是字串格式,
* 所以我們要透過toString進行轉換。
*/
let targetNum = (target - num).toString();
// 接著確認mapNumber是否有y的物件,如果沒有就針對2去產生當下的值。
if (mapNumber[targetNum] !== undefined) {
// 此時發現 y = 9 - x ,並且確認是有值那就回傳當前的key值。
return [mapNumber[target - num], i];
} else {
// 在這我們用值去當key,並且把key設定為值,這樣就能像上面去取得資料。
mapNumber[num] = i;
}
}
};

實作結果

最後再提交就能得出下面的結果,雖然我的不一定是最好解法,但能解決複雜度的問題,如果有更好的解法歡迎一起討論,我們下一個挑戰見!

Two SumTwo Sum