首页 > 代码库 > LeetCode - 1 - TwoSum

LeetCode - 1 - TwoSum

题目

URL:https://leetcode.com/problems/two-sum/

 

技术分享

 

解法

一、暴力破解

想不到任何方法的时候这是最好的方法。先做起来,再思考如何优化。

具体而言,有等式 target = a + b,第一个循环确定 a,第二个循环 a 的右面搜索 b,搜索到了就返回。

双层循环,时间复杂度O(n2),运行时间约为 41 ms。

    public int[] twoSum2(int[] nums, int target) {
        HashMap<Integer, Integer> contains = new HashMap<>();
        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;
    }

 

二、Hash(Best Solution)

上面的方法搜索值比较慢,因为是一个一个搜索的。如何减少搜索时间就成了关键。

这里可以采取 Hash 技术,在数组中遍历搜索,当搜索时,在集合里搜索需要搜索的值存不存在,若存在,返回当前下标和搜索到的值的下标,若不存在,将该数字以及下标加入集合。由于这里采用 Hash 方法搜索,故复杂度很低,只有 O(1),上面是一个循环,为 O(n)。

利用 Hash 搜索的算法时间只有一层循环,时间复杂度为 O(n),运行时间约为 8 ms。

    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> contains = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int right = target - nums[i];
            if (contains.containsKey(right)) {
                return new int[]{contains.get(right), i};
            } else {
                contains.put(nums[i], i);
            }
        }
        return null;
    }

 

总结

搜索的时候利用 Hash 技术可以更快。

 

LeetCode - 1 - TwoSum