题目:给定一个整数数组和一个整数,返回两个数组的索引,这两个索引指向的数字的加和等于指定的整数。需要最优的算法,分析算法的空间和时间复杂度

参考答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public int[] twoSum(int[] nums, int target) {
    if(nums==null || nums.length<2)
        return new int[]{0,0};
 
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i=0; i<nums.length; i++){
        if(map.containsKey(nums[i])){
            return new int[]{map.get(nums[i]), i};
        }else{
            map.put(target-nums[i], i);
        }
    }
 
    return new int[]{0,0};
}

分析:空间复杂度和时间复杂度均为 O(n)