LeetCode 解題練習：Two Sum (Easy)

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/two-sum/description/

中文描述

指定一個整數陣列 nums 以及一個整數 target，找出在陣列中的兩個整數總合為 target 之索引位置。可以假設每組測試資料剛好只有一組不重複的答案，且一個陣列元素只會使用一次。

範例一：

輸入 nums = [1, 3, 5, 9], target = 8

輸出 [1, 2]

因為 nums[1] + nums[2] = 3 + 5 = 8

範例二：

輸入 nums = [1, 3, 5, 2, 9], target = 10

輸出 [0, 4]

因為 nums[0] + nums[4] = 1 + 9 = 10

解法一：暴力法 Brute Force

使用迴圈找出陣列中任兩個元素 nums[i] + nums[j] 的總和是否等於 target 。

Python Code

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        eleLen = len(nums)

        for i in range(eleLen):

            for j in range(i + 1, eleLen):

                if nums[i] + nums[j] == target:

                    return [i, j]

C++ Code

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> ret;

        for(int i = 0; i < nums.size(); i++) {

            for(int j = i + 1; j < nums.size(); j++) {

                if( nums[i] + nums[j] == target ) {

                    ret.push_back(i);

                    ret.push_back(j);

                    return ret;

                }

            }

        }

        return ret;

    }

};

解法二：兩階段查表法 ( two-pass hash table)

第一階段將陣列元素的值當成查詢的鍵值 key，陣列元素的索引當成查詢的值 value。以 nums = [1, 3, 5, 9] 為例，將會建立一個如下的 hash table：

key	value
1	0
3	1
5	2
9	3

然後檢查  target - nums[i] 是否存在此 hask table 的鍵值中。

Python Code

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        hashTable = {}

        eleLen = len(nums)

       

        # First Pass

        for i in range(eleLen):

            hashTable[nums[i]] = i

       

        # Second Pass

        for i in range(eleLen):

            diff = target - nums[i]

            if diff in hashTable and hashTable[diff] != i:

                return [i, hashTable[diff]]

C++ Code

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> ret;

        map<int, int> hashTable;

        for(int i = 0; i < nums.size(); i++)

            hashTable[nums[i]] = i;

        for(int i = 0; i < nums.size(); i++) {

            int diff = target - nums[i];

            if( hashTable.find(diff) != hashTable.end() && hashTable[diff] != i )  {

                ret.push_back(i);

                ret.push_back(hashTable[diff]);

                return ret;

            }

        }

        return ret;

    }

};

解法三：一階段查表法 ( one-pass hash table)

在建立 hash table 時，可以先檢查  target - nums[i] 是否存在此 hash table 的鍵值中，再建立 hash table。

Python Code

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        hashTable = {}

        eleLen = len(nums)

       

        # One Pass

        for i in range(eleLen):

            diff = target - nums[i]

            if diff in hashTable:

                return [i, hashTable[diff]]

           

            hashTable[nums[i]] = i # 先檢查再建立 hash table

C++ Code

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> ret;

        map<int, int> hashTable;

        for(int i = 0; i < nums.size(); i++) {

            int diff = target - nums[i];

            if( hashTable.find(diff) != hashTable.end() )  {

                ret.push_back(i);

                ret.push_back(hashTable[diff]);

                return ret;

            }

            hashTable[nums[i]] = i; // 先檢查再建立 hash table

        }

        return ret;

    }

};