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]，就能得到我們要的答案了。