LeetCode 热题 HOT 100 Java题解——1. 两数之和_leetcode 热题 hot 100解析

1. 两数之和

题目:
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1
2
3
4

（1）暴力法

暴力法就是循环遍历数组的每一个数，针对每个数向后遍历剩余的数字，如果两数之和等于target，则返回两个数的下标：

import java.util.Arrays;

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 new int[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析

• 时间复杂度：$O(n^2)$

  双重循环，复杂度较高，耗时时间长

• 空间复杂度：$O(1)$

  无额外空间

（2）哈希表

哈希表可以优化第二遍循环中对元素的检索速度，使用HashMap可以将查找时间从$O(n)$近似降低至$O(1)$（如果出现冲突，查询速度退化至$O(n)$，通常分摊开销为$O(1)$ ）。
一次循环，如果没有可以和当前数字匹配的另一个数字（和等于target）就将当前数字存入哈希表，如果有就说明找到了该数字，返回即可。

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target - nums[i])) return new int[]{map.get(target - nums[i]), i};
            else map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No solution");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析

• 时间复杂度：$O(n)$

  一遍循环，查找哈希表使用$O(1)$。

• 空间复杂度：$O(n)$

  使用$O(n)$的额外哈希表空间。

（3）使用位运算快速哈希

有点投机取巧的办法，速度非常快，利用了位运算开辟了一个比较大的空间相当于进行了一个快速哈希，看看就行，不是很推荐

class Solution {
    public int[] twoSum(int[] nums, int target){
        int volume = 2<<10; //2048
        int bitNum = volume-1; //11111111111
        int[] res = new int[volume];
        for(int i=0;i<nums.length;i++){
            int c = (target-nums[i])&bitNum;
            if(res[c]!=0){
                return new int[]{res[c]-1,i};
            }
            res[nums[i]&bitNum] = i+1;
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

• 时间复杂度：$O(n)$

  一遍循环，访问res数组使用$O(1)$。

• 空间复杂度：$O(?)$

  使用题目测试样例数值大小的额外空间。