LeetCode—>两数之和
2022-09-22 22:45:36

之后的LeetCode的练习代码都会写在Gitee上：

hopeStation/leetcode

两数之和

使用普通循环的方式居然通不过LeetCode的测试，提示超时…（官方答案中的普通循环也不能通过..）

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
45
46
47
48
49
50
51
52
53
54

package top.hopestation;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LeetCode {
    //暴力循环法
    public static int[] twoSum1(int[] nums, int target) {
        int len = nums.length;
        for (int i = 0; i <len ; i++) {
            if(nums[i]>target){
                continue;
            }
            for (int j = i+1; j < len; j++) {
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }

    /**
     * 使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。
     * 这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，
     * 然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];

    }

    public static void main(String[] args) {
        int[] param = {1,2,5,3,4,7,};
        String res = Arrays.toString(twoSum2(param, 10));
        System.out.println(res);
    }
}



Prev
2022-09-22 22:45:36
Next