Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 1. Two Sum

發表於 分類於 ， ， Disqus：
我想這題是正要開始寫 LeetCode 的人，大部分的人的第一題吧，這題是個基本題算在 easy 的題型。

前言

　　我想這題是正要開始寫 LeetCode 的人，大部分的人的第一題吧，這題是個基本題算在 easy 的題型，看到題目直接就會想到使用雙迴圈的寫法，不過雙迴圈時間複雜度只有達到 O(N^2) 不那麼理想，如果比較資深的工程師會用 HashMap 做處理，這時時間複雜度可以達到 N(1)，這篇有 Java 和 Python 的寫法。

題目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to nums.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

給定一個整數陣列 nums 和一個整數結果 target，陣列中會有兩個元素加起來等於整數結果 target，回傳這兩個元素的位置。

你可能假設每個輸入只會對應一個答案，而且你不能使用同樣的元素兩次

你可以回傳任何順序的答案。

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

題目限制

同樣的元素不能使用兩次

2 <= nums.length <= 104
109 <= nums[i] <= 109
109 <= target <= 109

範例

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
1
2
Input: nums = [3,2,4], target = 6
Output: [1,2]
1
2
Input: nums = [3,3], target = 6
Output: [0,1]

思路&筆記

使用暴力的解法：雙迴圈

  1. 迴圈 1 取得第一個索引，迴圈 2 取得第二個索引

  2. 但迴圈 2 的循環起始需要做個 i+1，目的是元素不要重複到

  3. 當迴圈 2 的索引都循環完後，迴圈 1 的索引會換到下一個索引，以此類推

  4. 直到兩個索引的值加起來，等於目標整數 target，就把當下的索引回傳出來

JAVA 初階實現

使用暴力解法：雙迴圈

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i=0; i < nums.length; i++){
            for (int j = i+1; j < nums.length; j++){ // 元素不要重複到
                if(nums[i] + nums[j] == target){
                    return new int[] {i, j}; // 回傳索引
                }
            }
        }
        return new int[] {}; // 當找不到符合條件的組合時，回傳一個空的整數陣列
    }
}

JAVA 進階實現

筆者還在學習中，參考了討論區裡網友的解法，這裡有使用 HashMap 存資料。

如果目標整數是 9，想像一下兩個數是各左右一半，那麼 9 減掉其中一半會是另一半的話，答案就出來了，我們只是把答案先放在 HashMap 裡的 Key 的位置， Value 是對應的索引位置，那個判斷式就是判斷 HashMap 裡有沒有另外一半，有的話把 Value 輸出出來。

  • 遍歷時用 target 減掉當下索引的值，可以得出另一個整數。(這個就是我們要相加起來的另一個整數，沒有的話代表不是兩數的合)
  • 因第一次判斷 Map 本來就是空的一定不成功，所以把已判斷過的元素跟索引存進 Map 裡。(這裡要顛倒存，因為之後判斷時要取索引，索引放在值的地方)
  • 之後遍歷第二次時，判斷 .containsKey() 搜尋 Map 裡有無 key，這時 true 進入判斷式
  • .get() 取值 (剛顛倒存入的索引) → 0
  • i 則是當下的索引 → 1
  • 最後把兩個索引存入 new int[] 陣列中 [0, 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numToIndex = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 判斷鍵是否存在 Map
            if (numToIndex.containsKey(target - nums[i])) { // 目標整數 - 索引 1 的值
                // 回傳兩個索引
                return new int[] {numToIndex.get(target - nums[i]), i}; // numToIndex 裡的"值"是索引,當前 i 是索引
            }
            // 把前面的資料添加進 Map 
            numToIndex.put(nums[i], i);  // {2,0} (注意這邊是顛倒的存進去)
        }
        return new int[] 0; // 仍未找到符合要求的元素，則返回一個空的 int[] 陣列
    }
}

Python 初階實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)): # 索引從第2個開始
                if i != j and nums[i] + nums[j] == target: # 索引不要重複且索引值相加
                    return [i, j]
		return []

Python 進階實現

筆者還在學習中，參考了討論區裡網友的解法。
使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numToIndex = {} # 字典
        for i in range(len(nums)):
            # 判斷鍵是否存在 Map
            if target - nums[i] in numToIndex: # 目標整數 - 索引 1 的值
                return [numToIndex[target - nums[i]], i] 
            # 把前面的資料添加進字典
            numToIndex[nums[i]] = i # 鍵 nums[i] = 值 i
        return []

成績

Language Algorithm Runtime Memory
Java 初階實現 85 ms 42.7MB
Python 初階實現 4297 ms 14.9MB