原创文章转载请注明出处

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.

Example:

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

这道题我个人认为使用哈希表是比较经济实用的解决方式。类似C这样默认不支持HashMap的语言可以先对数组进行快速排序，再对已排序数组进行查找，复杂度也是O(n)，从执行效率上看也是C的方案最快。而Python往往能写出最简短的代码。

Swift

两重循环遍历，复杂度 O(n^2)。

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for var i in 0 ..< nums.count {
            for var j in i+1 ..< nums.count {
                if nums[i] + nums[j] == target {
                    return [i, j]
                }
            }
        }
        return [0,0]
    }
}

哈希表优化版，复杂度降低到O(n)。

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var hash: [Int : Int] = [:]
        for (i, n) in nums.enumerated() {
            if let index = hash[target - n] {
                return [index, i]
            }
            hash[n] = i
        }
        return []
    }
}

Go

func twoSum(nums []int, target int) []int {
  hash := make(map[int]int)
  for i, n := range nums {
    key := target - n
    if index, ok := hash[key]; ok {
      return []int{index, i}
    }
    hash[n] = i
  }
  return []int{}
}

Java

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

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let hashTable = {};
    for(let i=0; i<nums.length; i++){
        let num   = nums[i];
        let index = hashTable[target-num];
        if(index !== undefined) return [index, i]
        hashTable[num] = i;
    }
};

C

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
int *twoSum(int *nums, int numsSize, int target) {
    int i, j;
    int *ret;
    int *temp;
    ret = (int *) malloc(2 * sizeof(int));
    temp = (int *) malloc(numsSize * 2 * sizeof(int));
    for (i = 0; i < numsSize; i++) {
        temp[2 * i] = nums[i];
        temp[2 * i + 1] = i;
    }
    qsort(temp, numsSize, 2 * sizeof(temp[0]), cmp);
    i = 0;
    j = numsSize - 1;
    while (temp[2 * i] + temp[2 * j] != target) {
        if (temp[2 * i] + temp[2 * j] > target) {
            --j;
        } else if (temp[2 * i] + temp[2 * j] < target) {
            ++i;
        } else {
            break;
        }
    }
    ret[0] = temp[2 * i + 1] < temp[2 * j + 1] ? temp[2 * i + 1] : temp[2 * j + 1];
    ret[1] = temp[2 * i + 1] > temp[2 * j + 1] ? temp[2 * i + 1] : temp[2 * j + 1];
    return ret;
}

Python

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = { }
        for i, n in enumerate(nums):
            if target - n in d:
                return [min(i, d[target-n]), max(i, d[target-n])]
            d[n] = i

变态版，看看代码思路就好。执行效率比较低，原题没有要求遍历出所有结果，这个解法返回数据太多了，虽然能通过测试，但是时间比较长。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        l=len(nums)
        r=range(l)
        t=[x for x in r if (target-nums[x]) in (nums[:x]+nums[x+1:])]
        return t

我是咕咕鸡，一个还在不停学习的全栈工程师。
热爱生活，喜欢跑步，家庭是我不断向前进步的动力。