折腾一个Two_Sum（中）

16 Jan 2018

在这篇文章里，我仍旧聚焦Two Sum， 1. 通过数据结构和优化算法来降低复杂度（C++） 2. 在其他语言里调用现成的散列表 3. 在C里用数组浆糊一个散列表

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].

上次我的最天（bai）真（chi）解法，所有都通过了，除了Python3运行超时。没放弃，如果简单写两层for循环注定超时，那还有一个尝试项——用它的迭代器模块itertools。如果模块内部有优化的话，可能可以以语言的优秀特性来弥补思维上的不聪明。

Python3.x解一之itertools：

class Solution:
    import itertools
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        comb = itertools.combinations(nums,2)
        res = [x for x in comb if sum(y for y in x) == target]
        i = nums.index(res[0][0])
        j = nums.index(res[0][1],i+1)
        return [i,j]

如果输入nums=[3,3]，target=6，原来程序会返回[0,0]，但正确的结果是[0,1]，因为nums.index[3]返回0，后来发现index的第二个参数——开始搜索的下标，所以把它设成上一个结果的下标+1就可以得到第二个3的期待下标了。

Performance: Time Out

还是超时了，至少知道了python里的itertools并没有优化。现在就正式从数据结构上进行优化了，这到底是个什么问题，是搜索问题啊，过去我用了“挨个搜索”的遍历。现在想想我有什么要什么，有无序数列，要搜索，找下标，散列表浮现眼前，花费空间来优化时间，可以把时间复杂度从O(n²)降低到O(n)，散列表要存n个数值-下标对，空间复杂度从O(1)上升到O(n)。

C++解二——数据结构优化——2-Pass Hash Table：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        map<int,int> hash_table;
	//two-pass
        for (int i=0; i<nums.size(); i++){
            hash_table[nums[i]] = i;
        }
        for (int i =0; i<nums.size()-1; i++){
            int location = hash_table.find(target-nums[i])->second;
            if(location !=i && location != hash_table.end()->second){
                result.push_back(i);
                result.push_back(location);
                return result;
            }
        }
        throw std::invalid_argument("No solution"); 
    }
};

Performance: 19ms

上面的代码思路很简单，先构建数据结构后求解。用一个for循环来构建一个散列表。然后再用一次for来搜索求解。算上常数，时间复杂度是线性时间——2n。

算法问题上往往有“抖机灵”做法，透彻了解问题后然后想出解题思路，过程就是——想。

这道题里还可以“抖机灵”，我们需要完整的散列表吗？并没有，可以一边构建一边搜索，这样时间可以从2n下降到n，在设计算法时，时间复杂度往往是忽略掉常数项的，但在实战里，去掉一个for可以把运行时间减半。下面的代码就把运行时间从19ms减少到10ms。而空间上散列表的任务也从存储固定n对下降到最多n-1对。

C++解三——进一步算法优化——1-Pass Hash Table：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        map<int,int> hash_table;
	//one-pass
        for (int i=0; i<nums.size(); i++){
                int location = hash_table.find(target-nums[i])->second;
                if(location != hash_table.end()->second){
                result.push_back(location-1);
                result.push_back(i);
                return result;}  
                else{
                hash_table[nums[i]] = i+1;
                }
        }
        
        throw std::invalid_argument("No solution"); 
    }
        
};

Performance: 10ms

三种算法的时间对比：

placeholder

各语言的散列表实现：

下面是其他语言的解三。调用现成的HashMap函数（Dictionary），不研究散列函数和冲撞的处理。

Java解三：

class Solution {
       	public int[] twoSum(int[] nums, int target) {
                Map<Integer, Integer> map = new HashMap<>();
                for (int i = 0; i < nums.length; i++) {
                	int x = target - nums[i];
                        if (map.containsKey(x)) {
                                return new int[] { map.get(x), i };
                        }
                map.put(nums[i], i); 
        	}
        	throw new IllegalArgumentException("No two sum solution");
	}
}

Performance:9ms

Python2.x/3.x解三：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        map={}
        for i in range ( 0, len(nums) ):
            x = target - nums[i]
            if x in map:
                return [map[x], i]
            else:
                map[nums[i]] = i 
        raise ValueError("No solution")

Performance: python2 40ms python3 63ms

Javascript解三：

var twoSum = function(nums, target) {
        var map = {}
        for (var i=0; i<nums.length; i++){
                x = target - nums[i];
                if (x in map){
                        return [map[x], i]; 
                }
                else{
                        map[nums[i]]=i;
                }
        }
        throw new Error("No solution");    
};

Performance: 97ms

Ruby解三：

def two_sum(nums, target)
    map = {}
    nums.each_with_index do |num, i|
        key = ((map.select { |k,v| v == (target-num)}.keys)) 
        key.empty? ? false : (return [key, i].flatten)
        map[i]=num
    end 
    return "No solution"
end

Performace: 2845ms

Go解三：

twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i := 0; i< len(nums); i++ {
        x := target - nums[i]
        if _, ok := m[x]; ok {
                return []int{m[x],i}
        } else {
                m[nums[i]] = i 
        }
    }   
    return nil 
}

Performance: 12ms

Swift解三：

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var map = [Int:Int]()
        var result = [Int]()
        for i in 0..<nums.count{
                let x = target - nums[i]
                if let j = map[x] {
                        result.append(j)
                        result.append(i)
                        return result   
                } else {
                        map[nums[i]]=i
                }
         }
         return result    
    }   
}

Performance: 24ms

C#解三：

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
       var map = new Dictionary<int,int?>();
       for (int i=0; i<nums.Length; i++){
                int x = target - nums[i];
                if (map.ContainsKey(x)){
                        return new int[] { map[x].Value, i};    
                } else {
                        map[nums[i]] = i;
                }
        }
        throw new ArgumentNullException("No solution");    
    }   
}

Performance: 518ms

注释：需要空间名称using System.Collections.Generic;

Kotlin解三：

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = HashMap<Int, Int>()
        for( i in 0..nums.size-1){
                var x = target - nums[i]
                if (map.containsKey(x)) {
                        return intArrayOf(map.get(x)!!,i)
                } else {
                        map.put(nums[i],i)
                }
        }
        return intArrayOf()    
    }   
}

Performance: 498ms

注释：Kotlin如果遇上type mismatch: inferred type is Int? but Int was expected，在确认数值非空的情况下，可以用操作符!!或者.safe()来转换成Int。

C里用数组假装散列表

如果这道题我需要它最快，不计代价地最快，那我有什么选项？

最快的搜索，所以用数组的offset，从地址直接得到值。代价是冗余内存，把数组长度控制在max=target-min,len=max-min+1

C解三：

int* twoSum(int* nums, int numsSize, int target) {   
        //Array to imitate a HashMap
        int min = INT_MAX;
        for (int i = 0; i < numsSize; i++) {   
            if (nums[i] < min)  
                min = nums[i];  
        }
        int max = target - min;  
        int len = max - min + 1;
        int *table = (int*)malloc(len*sizeof(int));  
        memset(table, -1, len*sizeof(int));
    
        static int result[2] = { -1,-1 };    
        for (int i = 0; i < numsSize; i++) {
                //ignoring outliner to save space
                if (nums[i]-min < len) {
                        int x = target -nums[i] - min;
                        if (table[x] != -1) { 
                                result[0] = table[x];  
                                result[1] = i;  
                                return result;  
                        }
                        table[nums[i]-min] = i;  
                }
        }
        free(table);  
        return NULL;  
}

Performance: 4ms

注释：果然最快，这算法出处雅可的博客，我改动了一下。快是快了，击败了91.41%的提交，但是空间关联输入数据，不仅非常大，而且还有不可控的代价。

不专业分析：