怎么用LeetCode實現求兩數之和

這篇文章主要介紹“怎么用LeetCode實現求兩數之和”，在日常操作中，相信很多人在怎么用LeetCode實現求兩數之和問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么用LeetCode實現求兩數之和”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

描述

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 的那 兩個 整數，并返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。

你可以按任意順序返回答案。

示例 1：

輸入：nums = [2,7,11,15], target = 9 輸出：[0,1] 解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2：

輸入：nums = [3,2,4], target = 6 輸出：[1,2] 示例 3：

輸入：nums = [3,3], target = 6 輸出：[0,1]

Solution

數組nums中存在兩個下標的值相加的和等于target目標值，找到這兩個數字并返回下標，并且答案中不能出現相同的元素坐標，即每個元素下標不能重復

暴力解法

暴力解法

思路

暴力解法，直接雙重for循環，循環不重復，第一層for循環從0到(length-1)，第二層for循環從第一層定義的開始+1到length，取出第一層循環的值和第二層循環的值，相加等于target則記錄下標并返回

CODE

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

復雜度

• 時間復雜度：O(N^2)，其中 N 是數組中的元素數量。最壞情況下數組中任意兩個數都要被匹配一次

• 空間復雜度：O(1)

結果

執行用時：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶

內存消耗：38.7 MB, 在所有 Java 提交中擊敗了35.39%的用戶

哈希表

哈希表

思路

暴力解法的弊端在于x + y == target的時間復雜度過高，我們需要快速找到x對應的y(target-x)是否存在，即快速找到對應的索引，哈希表則是一個很好的選擇，利用哈希表將當前值x以及對應下標i存儲起來，對于遍歷的每個x，先查詢在哈希表中是否有對應的y(target-x)，沒有則將x存入到哈希表中，保證x不會和自己匹配

CODE

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
          	//首先檢查哈希表中是否有對應的y(target-x)
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
          	//存儲當前值和對應下標
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

復雜度

• 時間復雜度：O(N)，其中 N 是數組中的元素數量。對于每一個元素 x，我們可以 O(1) 地尋找 target - x

• 空間復雜度：O(N)，其中 N 是數組中的元素數量。主要為哈希表的開銷

結果

執行用時：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶

內存消耗：38.7 MB, 在所有 Java 提交中擊敗了47.28%的用戶

到此，關于“怎么用LeetCode實現求兩數之和”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！