Two Sum

題目描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice

Example

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

中文描述

給定一個(gè)數(shù)組和一個(gè)目標(biāo)值蒲跨，返回和為目標(biāo)值的兩個(gè)數(shù)的索引值列粪。假設(shè)每一個(gè)輸入都有一個(gè)確定結(jié)果贷帮，同一個(gè)元素?zé)o法使用兩次

解題方案

1. 首先想到的就是brute force算法，兩層的循環(huán)解決問(wèn)題屎飘，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為常數(shù)。代碼如下

public int[] twoSum(int[] nums, int target) {
    int[] answer= new int[2];
    for(int i=0;i<nums.length;i++){
        answer[0]=nums[i];
        int temp = target-answer[0];
        for(int j=i;j<nums.length;j++){
            if(nums[j]==temp){
                return answer;
            }
        }
    }
    return answer;
}

2. 第二種方案就是考慮如何優(yōu)化上一種算法了,這里看到網(wǎng)上的采用HashMap的方式來(lái)優(yōu)化算法的時(shí)間復(fù)雜度章钾。

利用的是HashMap取數(shù)據(jù)時(shí)間是常數(shù)時(shí)間。

public int[] twoSum2(int[] nums, int target) {
   int[] res = new int[2];
   if(numbers==null||numbers.length<2) return null;
   Map<Integer, Integer> map = new HashMap<>();
   for(int i=0;i<numbers.length;i++){
       if(map.containsKey(target-numbers[i])){
           res[0]=map.get(target-numbers[i])+1;
           res[1]=i+1;
           return res;
       }
       map.put(numbers[i],i);
   }
   return null;
}

因?yàn)橹皩?duì)于Java集合類(lèi)的基礎(chǔ)了解不夠热芹，所以不太理解所謂的HashMap取值操作為常數(shù)時(shí)間贱傀。于是查閱了相關(guān)資料,現(xiàn)記錄一下。

Java HashMap 是基于哈希表的Map接口實(shí)現(xiàn)伊脓，以Key-Value的形式在HashMap中府寒，key-value總是會(huì)當(dāng)做一個(gè)整體來(lái)處理，系統(tǒng)會(huì)根據(jù)hash算法來(lái)來(lái)計(jì)算key-value的存儲(chǔ)位置报腔，我們總是可以通過(guò)key快速地存株搔、取value。下面就來(lái)分析HashMap的存取纯蛾。

HashMap的構(gòu)造函數(shù)

HashMap()：構(gòu)造一個(gè)具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap纤房。
HashMap(int initialCapacity)：構(gòu)造一個(gè)帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個(gè)帶指定初始容量和加載因子的空 HashMap翻诉。

其中關(guān)于初始容量和加載因子和其他數(shù)據(jù)結(jié)構(gòu)的概念相同炮姨，初始容量是創(chuàng)建哈希表d額初始大小，加載因子表示哈希表的最大填充程度碰煌。也就是當(dāng)哈希表達(dá)到這個(gè)填充程度的時(shí)候舒岸，就需要對(duì)哈希表進(jìn)行擴(kuò)容。

HashMap存儲(chǔ)

下面簡(jiǎn)單看一下hashMap的put方法源碼

public V put(K key, V value) {
    //當(dāng)key為null芦圾，調(diào)用putForNullKey方法吁津，保存null與table第一個(gè)位置中，這是HashMap允許為null的原因
    if (key == null)
        return putForNullKey(value);
    //計(jì)算key的hash值
    int hash = hash(key.hashCode());                  ------(1)
    //計(jì)算key hash 值在 table 數(shù)組中的位置
    int i = indexFor(hash, table.length);             ------(2)
    //從i出開(kāi)始迭代 e,找到 key 保存的位置
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        //判斷該條鏈上是否有hash值相同的(key相同)
        //若存在相同，則直接覆蓋value碍脏，返回舊value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;    //舊值 = 新值
            e.value = value;
            e.recordAccess(this);
            return oldValue;     //返回舊值
        }
    }
    //修改次數(shù)增加1
    modCount++;
    //將key梭依、value添加至i位置處
    addEntry(hash, key, value, i);
    return null;
}

通過(guò)源碼我們可以清晰看到HashMap保存數(shù)據(jù)的過(guò)程為：首先判斷key是否為null，若為null典尾，則直接調(diào)用putForNullKey方法役拴。若不為空則先計(jì)算key的hash值，然后根據(jù)hash值搜索在table數(shù)組中的索引位置钾埂，如果table數(shù)組在該位置處有元素河闰，則通過(guò)比較是否存在相同的key，若存在則覆蓋原來(lái)key的value褥紫，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）姜性。若table在該處沒(méi)有元素，則直接保存髓考。保存的過(guò)程看起來(lái)十分簡(jiǎn)單部念，但是其中有一部分比較重要的就是求Hash值函數(shù)

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

對(duì)于HashMap的table而言，數(shù)據(jù)分布需要均勻（最好每項(xiàng)都只有一個(gè)元素氨菇，這樣就可以直接找到）儡炼，不能太緊也不能太松，太緊會(huì)導(dǎo)致查詢速度慢查蓉，太松則浪費(fèi)空間乌询。計(jì)算hash值后，怎么保證數(shù)據(jù)的分布呢豌研？HashMap調(diào)用indexFor方法妹田。

static int indexFor(int h, int length) {
   return h & (length-1);
}

這個(gè)函數(shù)我在一開(kāi)始沒(méi)有理解到底什么意思，通過(guò)看別人的講解后發(fā)現(xiàn)這個(gè)函數(shù)的作用和取模運(yùn)算是相同的鹃共。具體計(jì)算的結(jié)果可以看下面的表格秆麸。

從上面的圖表中我們看到總共發(fā)生了8此碰撞，同時(shí)發(fā)現(xiàn)浪費(fèi)的空間非常大及汉，有1、3屯烦、5坷随、7、9驻龟、11温眉、13、15處沒(méi)有記錄翁狐，也就是沒(méi)有存放數(shù)據(jù)类溢。這是因?yàn)樗麄冊(cè)谂c14進(jìn)行&運(yùn)算時(shí)，得到的結(jié)果最后一位永遠(yuǎn)都是0，即0001闯冷、0011砂心、0101、0111蛇耀、1001辩诞、1011、1101纺涤、1111位置處是不可能存儲(chǔ)數(shù)據(jù)的译暂，空間減少，進(jìn)一步增加碰撞幾率撩炊，這樣就會(huì)導(dǎo)致查詢速度慢外永。而當(dāng)length = 16時(shí)，length – 1 = 15 即1111拧咳，那么進(jìn)行低位&運(yùn)算時(shí)伯顶，值總是與原來(lái)hash值相同，而進(jìn)行高位運(yùn)算時(shí)呛踊，其值等于其低位值砾淌。所以說(shuō)當(dāng)length = 2^n時(shí)，不同的hash值發(fā)生碰撞的概率比較小谭网，這樣就會(huì)使得數(shù)據(jù)在table數(shù)組中分布較均勻汪厨，查詢速度也較快。

讀取的實(shí)現(xiàn)

相對(duì)于HashMap的存而言愉择，取就顯得比較簡(jiǎn)單了劫乱。通過(guò)key的hash值找到在table數(shù)組中的索引處的Entry，然后返回該key對(duì)應(yīng)的value即可锥涕。

public V get(Object key) {
    // 若為null衷戈，調(diào)用getForNullKey方法返回相對(duì)應(yīng)的value
    if (key == null)
        return getForNullKey();
    // 根據(jù)該 key 的 hashCode 值計(jì)算它的 hash 碼  
    int hash = hash(key.hashCode());
    // 取出 table 數(shù)組中指定索引處的值
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        //若搜索的key與查找的key相同，則返回相對(duì)應(yīng)的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

從上面的代碼當(dāng)中我們就可以得到為什么HashMap可以以常數(shù)的時(shí)間進(jìn)行存取數(shù)據(jù)了层坠。

再寫(xiě)這篇文章的時(shí)候殖妇，在CSDN的博客發(fā)現(xiàn)了另外的解法，

先對(duì)數(shù)組進(jìn)行排序破花，然后使用夾逼的方法找出滿足條件的pair谦趣，原理是因?yàn)閿?shù)組是有序的，那么假設(shè)當(dāng)前結(jié)果比target大座每，那么左端序號(hào)右移只會(huì)使兩個(gè)數(shù)的和更大前鹅，反之亦然。所以每次只會(huì)有一個(gè)選擇峭梳，從而實(shí)現(xiàn)線性就可以求出結(jié)果舰绘。該算法的時(shí)間復(fù)雜度是O(nlogn+n)=O(nlogn)，空間復(fù)雜度取決于排序算法。

public int[] twoSum(int[] numbers, int target) {
    int[] res = new int[2];
    if(numbers==null || numbers.length<2)
        return null;
    Arrays.sort(numbers);
    int l = 0;
    int r = numbers.length-1;
    while(l<r)
    {
        if(numbers[l]+numbers[r]==target)
        {
            res[0] = number[l];
            res[1] = number[r];
            return res;
        }
        else if(numbers[l]+numbers[r]>target) r--;
        else l++;
    }
    return null;
}

參考鏈接

1. http://blog.csdn.net/linhuanmars/article/details/19711387
2. http://www.cnblogs.com/chenssy/p/3521565.html

項(xiàng)目GitHub鏈接
https://github.com/yanqinghe/leetcode/blob/master/leetcodeJava/src/Two_Sum_1/Solution.java

PS：寫(xiě)在后面捂寿，現(xiàn)在開(kāi)始補(bǔ)寫(xiě)文檔記錄刷leetcode的過(guò)程口四，也希望能把自己的想法記錄下來(lái)與別人分享，同時(shí)也希望能夠與更多的人交流者蠕。
GitHub主頁(yè)https://github.com/yanqinghe/leetcode