題目描述

給定一個(gè)整數(shù)數(shù)組 nums?和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那?兩個(gè)?整數(shù)，并返回他們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，數(shù)組中同一個(gè)元素不能使用兩遍。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

題目分析

暴力搜索的方法是遍歷所有的兩個(gè)數(shù)字的組合，然后算其和，這樣雖然節(jié)省了空間，但是時(shí)間復(fù)雜度高。

一般來說，為了提高時(shí)間的復(fù)雜度，需要用空間來換，這算是一個(gè) trade off 吧，但這里只想用線性的時(shí)間復(fù)雜度來解決問題，就是說只能遍歷一個(gè)數(shù)字，那么另一個(gè)數(shù)字呢，可以事先將其存儲(chǔ)起來，使用一個(gè) HashMap，來建立數(shù)字和其坐標(biāo)位置之間的映射。

由于 HashMap 是常數(shù)級(jí)的查找效率，這樣在遍歷數(shù)組的時(shí)候，用 target 減去遍歷到的數(shù)字，就是另一個(gè)需要的數(shù)字了，直接在 HashMap 中查找其是否存在即可。

暴力求解

暴力法很簡單，遍歷每個(gè)元素 xx，并查找是否存在一個(gè)值與 target - xtarget?x 相等的目標(biāo)元素。

public int[] twoSum(int[] nums, int target) {

         //注意判空
         if(nums==null || nums.length==0){
             return null;
         }

        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 null;

    }

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n^2)

對(duì)于每個(gè)元素，我們?cè)噲D通過遍歷數(shù)組的其余部分來尋找它所對(duì)應(yīng)的目標(biāo)元素，這將耗費(fèi) O(n)O(n) 的時(shí)間。因此時(shí)間復(fù)雜度為 O(n^2)。

空間復(fù)雜度：O(1)。

哈希表兩次遍歷

注意要判斷查找到的數(shù)字不是第一個(gè)數(shù)字，比如 target 是4，遍歷到了一個(gè)2，那么另外一個(gè)2不能是之前那個(gè)2，整個(gè)實(shí)現(xiàn)步驟為：先遍歷一遍數(shù)組，建立 HashMap 映射，然后再遍歷一遍，開始查找，找到則記錄 index。

哈希表中對(duì)應(yīng)的存儲(chǔ)，key是元素，value是其下標(biāo)，這樣在二次遍歷時(shí)可以通過對(duì)比下標(biāo)排除同一個(gè)元素。

 public int[] twoSum(int[] nums, int target) {
         if(nums==null || nums.length==0){
             return null;
         }

        HashMap<Integer,Integer> map=new HashMap();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],i);
        }
        
        //兩次遍歷
        for(int i=0;i<nums.length;i++){
            int sub=target-nums[i];
            if(map.containsKey(sub) && map.get(sub)!=i){
                return new int[]{i,map.get(sub)};
            }
        }
        return null;
    }

哈希表一次遍歷

這種方式不需要考慮額外的重復(fù)判重。文章來源地址http://www.zghlxwxcb.cn/news/detail-424811.html

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
        //注意是target作為減數(shù)
            int diff = target - nums[i];
            if (map.containsKey(diff)) {
                return new int[] { map.get(diff), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

到了這里，關(guān)于LeetCode 1. Two Sum 兩數(shù)之和的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！