LeetCode #1 Two Sum 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

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

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),回傳陣列的兩個索引讓陣列值相加為整數目標值

你可以認為每個輸入都只有一種解答,而且同一個陣列元素不得使用超過一次

可以用任何順序回傳答案(無升降冪限制)

LeetCode #1 Constraints
題目限制

陣列長度為介於2到104 之間 ->不需考慮特殊情況(陣列無值或僅有一值的情況)

陣列內元素的值介於-109 到 109 之間

整數目標值 亦介於-109 到 109 之間

只有一種有效的答案存在

現在來看下範例

LeetCode #1 官方範例
官方範例

官方共提供3個範例,這題算是容易理解的

以範例2為例

要從給予的陣列nums找出相加為target : 6 的數字

似乎看一眼就能知道是第二個跟第三個數字

故答案應回傳 1 跟 2 (Array 陣列元素從0開始編號,故第一個為index 0,第二個為1,以此類推)


解題思路

先不論程式,直覺來想應該怎麼做

相信大多數人都會說出,先找第一個數字,再從剩下的數字找到能不能加總到整數目標值(target)

要是第一個數字搭配剩下的都沒找到,那就換第二個數字開始,一路找到結束為止

C# 解決方案

方案1 – 使用遞迴來尋找

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        
        int max = nums.Length;                  //陣列的長度
        
        for(int i = 0;i<max;i++)                //從第一個元素開始找
        {
            int diff = target - nums[i];        //這一次遞迴跟target的差異值,後面就不用一直計算了
            for(int j = i+1;j<max;j++)          //j = i+1 (因為不能用同個元素,故從下一個開始)
            {
                if(nums[j] == diff)             //當nums[j] = 剛剛得出的差異值時,回傳答案
                {
                    return new int[2]{i,j};
                }

            }        
        }
        return  new int[2]{0,0};                //其實不會跑到的地方,因所有路徑都須回傳值而加上
    }
}

時間複雜度 : O(n2)

方案2 – 使用內建的Array.FindIndex

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        
        int max = nums.Length;                  //陣列的長度
        int index;
        
        for(int i = 0;i<max;i++)                
        {

            //跟target的差異值
            int diff = target - nums[i];        
            index = Array.FindIndex(nums,i+1,x=>x == diff);
            
            //如果有找到差異值 (Array.FindIndex回傳非-1)
            if(index != -1)
            {
                return new int[2]{i,index};
            }
        }
        return  new int[2]{0,0};
    }
}

有別於解法一中,透過遞迴慢慢地去查,這裡直接用Array.FindIndex 即可回傳需要的索引 (查不到會回傳 -1)

方案3(推薦) – 使用 Dictionary

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> dict = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++)
        {
            int diff = target - nums[i];
            if (dict.ContainsKey(diff))
            {
                return new int[] {dict[diff], i};
            }
            if (!dict.ContainsKey(nums[i]))
            {
                dict.Add(nums[i], i);
            }
        }
        return new int[]{0,0};
    }
}

時間複雜度 : O(n) ➡ C# Dictionary ContainsKey O(1)

Dictionary 中的Key存的是 int值,Value則是存其index

直接用字典的ContainsKey 來判斷差異值是否存在,若有就取得其index並回傳

Java解決方案

方案1

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int max = nums.length;
        
        for(int i = 0;i<max;i++)
        {
            int diff = target - nums[i];
            for(int j=i+1;j<max;j++)
            {
                if(nums[j] == diff)
                {
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{0,0};
    }
}

方案2 ➡ 轉成List 然後sublist來模擬 C# findindex 可以設定startindex的功能

❌概念上沒問題,但運行時間會過久而導致 Time Limit Exceeded 的錯誤 (所有的測試案例都可以通過)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int max = nums.length;
        int index;
        List<Integer> myList = new ArrayList<>();
        
        for(int i = 0;i<max-1;i++)
        {
            int diff = target - nums[i];
            
            myList = IntStream.of(nums).boxed().collect(Collectors.toList());
            myList = myList.subList(i+1,max);
            index = myList.indexOf(diff);

            if(index != -1)
            {
                return new int[]{i,index+i+1};
            }
        }
        return new int[]{0,0};
    }
}

方案3(推薦) – 使用 HashMap來儲存

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
       HashMap<Integer, Integer>map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++)
        {
            int diff = target - nums[i];
            
            if (map.containsKey(diff))
            {
                return new int[] {map.get(diff), i};
            }
            else
            {
                map.put(nums[i], i);
            }
                
        }
        return new int[]{0,0};
    }
}

⭐運行時間 – 3ms

Python3 解決方案

方案1 (不太推薦) ➡ 高機率會跑到逾時,運氣好會成功(?

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            left = nums[i+1:]
            for j in range(len(left)):
                if (nums[i] + left[j]) == target:
                    return i, j+i+1

方案2 – hash table

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table={}
        for i in range(len(nums)):     #First, create the hash table 
            hash_table[nums[i]]=i

        for i in range(len(nums)):
            if target-nums[i] in hash_table:
                if hash_table[target-nums[i]] != i:
                    return [i, hash_table[target-nums[i]]]
        return [0,0]

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
        for(var i = 0 ; i < nums.length ; i++){
        var v = nums[i];

        for(var j = i+1 ; j < nums.length ; j++ ){
            if(  nums[i] + nums[j]  == target ){
                return [i,j];
            }
        }

    }
};

一樣有著不太優的時間複雜度 O(n2)

方案2 – 用map來存,與C#的Dictionary類似

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var map = {};
    for(var i = 0 ; i < nums.length ; i++){
        var n = nums[i];

        if(map[target-n] >= 0){
            return [map[target-n],i]
        } 
        else {
            map[n] = i;   //use map to store the value and index position
        }
    }
};

結論

相信很多人看到這題都會想說很簡單吧

但在按下送出鍵之後發現怎麼自己的寫法跑的這麼慢(假設只用巢狀迴圈)

歡迎你們OuO

歡迎來到工程師的世界,各位菜鳥們

寫出程式不難,但如何越寫越好永遠都是工程師的課題

這裡看下一題 ➡ LeetCode #2 Add Two Numbers 兩個數字加總 – Zyrastory-當程式碰上美食

🧡如果這篇文章有幫上你的一點點忙,那是我的榮幸

🧡可以的話,幫我的FaceBook 粉絲專頁按個讚,我會很感謝的

✅如有任何疑問,歡迎透過留言或messenger讓我知道 !

最新文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *