【leetcode常见面试题】1. 两数之和

【主要考察点】：哈希表

解题方法

1. 直接遍历

直接两层for循环遍历即可

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i<nums.length; i++){
            for(int j = i + 1; j<nums.length; j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

直接遍历的解法时间复杂度为O(n^2)，为能满足进阶要求

2. 哈希表

利用哈希表实现复杂度为O(n)的解法

class Solution {
    public int[] twoSum(int[] nums, int target) {
    	// Key为值，Value为下标
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i<nums.length; i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{i, map.get(target-nums[i])};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13