TwoSum

今天开始刷leetcode，第一篇博客就从第一道题开始吧~
描述：给一个整数数组，返回两个数的索引，使他们相加等于target，有且只有一个解。
举例：
nums = [2, 7, 11, 15], target = 9,
因为 ：nums[0] + nums[1] = 2 + 7 = 9;
return [0, 1]

最容易想的就是暴力求解~
暴力法（时间复杂度O(n2)）：

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

显然时间复杂度过高了。

参考了一下时间复杂度O(n)的方法，那就是利用HashMap。遍历数组，建立Map映射，在遍历时寻找满足条件的值（即target - a = b）:

public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < numbers.length; i++) {
        //如果此映射包含指定键的映射关系，则返回 true
        if (map.containsKey(target - numbers[i])) {
            result[1] = i;
            //返回指定键所映射的值；如果此映射不包含该键的映射关系，则返回 null
            result[0] = map.get(target - numbers[i]);
            return result;
        }
        //将指定的值与此映射中的指定键关联
        map.put(numbers[i], i);
    }
    return result;
}

当然，还可以用python~就是慢了点：
因为python字典也是一个hash table，所以索引的时间复杂度是O(1)，因此这么写的复杂度也是O(n)

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}
        for i in range(len(nums)):
            if nums[i] in dict:
                return [dict[nums[i]], i]
            else:
                dict[target - nums[i]] = i