力扣-1-数组中两个数的和为给定值

评论

题目：
1. Two Sum (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.

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

题目大意：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

解题思路：
首先想到的思路肯定是时间复杂度为O(n^2)的两次从头循环数组，这个方法很简单，但是效率很低。或者双指针或二分查找，复杂度为O(nlogn),效率也不高。
这里使用一种基于哈希表的方法，时间复杂度为O(n),空间复杂度为O(n),是一种用空间换时间的方法。
用哈希表存储元素(键)和其索引(值)，在访问到nums[i]时，判断HashMap中是否存在target-nums[i],如果存在，则说明target-nums[i]的索引和下标i就是要找的两个数。
详见代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Java:
//常规暴力遍历O(n^2)
public int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        for(int i = 0;i<nums.length - 1;i++){
            target -= nums[i];
            for(int j = i+1;j<nums.length;j++){
                if(target == nums[j]){
                    
                    ret[0] = i;
                    ret[1] = j;
                    return ret;
                }
            }
            target += nums[i];
        }
        return ret;
    }


//遍历一遍哈希表，时间复杂度O(n)
public int[] twoSum(int[] nums, int target){
    HashMap<Integer,Integer> indexForNum = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
      if(indexForNum.containsKey(target - nums[i])){
        /* map中的containsKey（key）方法是判断该key在map中是否有key存在。如果存在则返回true。如果不存在则返回false。
          
          Map集合允许值对象为null，并且没有个数限制，所以当get()方法的返回值为null时，可能有两种情况，
          一种是在集合中没有该键对象，另一种是该键对象没有映射任何值对象，即值对象为null。
          因此，在Map集合中不应该利用get()方法来判断是否存在某个键，而应该利用containsKey()方法来判断
        */
        return new int[]{indexForNum.get(target - nums[i]),i};
      }else{
        indexForNum.put(nums[i],i);
      }
    }
    return null;
}
//Map的常用方法：
//    map.containsKey(key);
//    value = map.get(key);
//    map.put(key,value);

Python:

InstantCWeedStudent

个人简介。