Try   HackMD

LeetCode - 1. Two Sum

tags: LeetCode Guide C++ Easy

原題連結: https://leetcode.com/problems/two-sum/

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.

範例測資

Example 1.

Input:

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

Output:

[0, 1].

Explanation:

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

說明

身為整個題庫的第一題,這題就是小case啦。

題目會指定一個數字target,要在array中找到2個數,加起來正好等於target,並回傳他們的索引值。

Code與解析

做法1. Brute Force [Accept]

Runtime: 260 ms > faster than 9.90%
Memory: 9.1 MB > less than 99.73%

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i < nums.size(); i++){ for(int j = 0; j < nums.size(); j++){ if(i != j && nums[i] + nums[j] == target) return {i, j}; } } return {}; } };

簡單利用兩層的迴圈,把整個array中的值兩兩配對過一遍,直到找到符合的項目為止。
因為測資不挑,所以即使是效率較差的暴力法也能AC。

做法2. One-pass Hash [Accept]

Runtime: 8 ms > faster than 92.99%
Memory: 10.1 MB > less than 50.95%

class Solution { private: map<int, int> index; public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i < nums.size(); i++){ if(index.find(target - nums[i]) == index.end()){ index[nums[i]] = i; } else{ return {index[target - nums[i]], i}; } } return {-1, -1}; } };

這個做法也不難,而且因為只要讀過一次array,所需時間不會太多。
做法是在讀取的同時,把"哪個數字在哪裡出現過"這件事給記下來,這樣之後需要的時候就不必再遍歷一次,直接到對應的index找就好了。
舉例來說,若題目為:

Array: [2, 15, 7, 1]
Target: 9

第一個會讀到的是2,那因為沒有先前的數字,所以理所當然的找不到9-2=7的對應值。
那這時我們就會把"2出現在index=0"這件事給記下來:

map<int, int> index;
index[2] = 0;

第二個會讀到的是15,同樣的,我們沒有找到9-15=-7的對應值,所以也要把15記下來:

index[15] = 1;

下一個會讀到7,這次我們會發現9-7=2已經被記錄過了,所以存取index[2],就能得到我們要的答案了。