LeetCode
Guide
C++
Easy
Difficulty: Easy
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.
Given nums = [2, 7, 11, 15], target = 9,
[0, 1].
Because nums[0] + nums[1] = 2 + 7 = 9, so return [0, 1].
身為整個題庫的第一題,這題就是小case啦。
題目會指定一個數字target,要在array中找到2個數,加起來正好等於target,並回傳他們的索引值。
Runtime: 260 ms > faster than 9.90%
Memory: 9.1 MB > less than 99.73%
簡單利用兩層的迴圈,把整個array中的值兩兩配對過一遍,直到找到符合的項目為止。
因為測資不挑,所以即使是效率較差的暴力法也能AC。
Runtime: 8 ms > faster than 92.99%
Memory: 10.1 MB > less than 50.95%
這個做法也不難,而且因為只要讀過一次array,所需時間不會太多。
做法是在讀取的同時,把"哪個數字在哪裡出現過"這件事給記下來,這樣之後需要的時候就不必再遍歷一次,直接到對應的index找就好了。
舉例來說,若題目為:
Array: [2, 15, 7, 1]
Target: 9
第一個會讀到的是2,那因為沒有先前的數字,所以理所當然的找不到9-2=7的對應值。
那這時我們就會把"2出現在index=0"這件事給記下來:
第二個會讀到的是15,同樣的,我們沒有找到9-15=-7的對應值,所以也要把15記下來:
下一個會讀到7,這次我們會發現9-7=2已經被記錄過了,所以存取index[2],就能得到我們要的答案了。