题干:

难度:Easy

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

解析:

由于已经确定了结果是确定的且必然只有一个,我们很容易便可以想到使用双层循环来解决问题,足够暴力也足够可行。当然,在这一题上使用这一时间复杂度为O(n^2)的算法的效率是可想而知的。很自然地,我们会想到利用HashMap来解决这一问题,因为HashMap的查找效率是常数级的。思路是建立数组元素与索引的映射(Hash),遍历数组,针对某一元素n,若在hash表的keys中有target-n存在,则可得到答案,否则以数组元素与索引值为key-value插入hash表,并继续遍历。

Java解法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> h=new HashMap<Integer,Integer>();
        int[] res=new int [2];
        for(int i=0;i<nums.length;i++){
            //查找hash表中是否有符合条件的结果,如果没有,将当前的数组元素和索引作为兼职对加入hash表中
            if (h.containsKey(target-nums[i])){
                res[0]=i;
                res[1]=h.get(target-nums[i]);
                break;
            }
            h.put(nums[i],i);
        }
        return res;
    }
}

Python解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        h={}
        res=[]
        for i in range(len(nums)):
            if target-nums[i] in h.keys():
                res.append(i)
                res.append(h[target-nums[i]])
                break
            h[nums[i]]=i
        return res
最后修改:2020 年 01 月 21 日 10 : 53 PM