一起LeetCode--两数之和

1、方法一：暴力求解

该方法非常简单，就是两层for循环，遍历所有组合获取有效解，代码如下：

/**

 

     * 暴力求解法

 

     * @param nums   源数组

 

     * @param target 目标值

 

     * @return

 

     */

 

    public int[] forceFind(int[] nums, int target) {

 

        

 

        for(int i=0; i<nums.length; ++i) {

 

            for(int j=i+1; j<nums.length; ++j) {

 

                if(target == (nums[i] + nums[j])) {

 

                    return new int[] {i, j};

 

                }

 

            }

 

        }

 

        

 

        throw new IllegalArgumentException("No Answer!");

 

    }

运行效果如图示。

时间复杂度 : O(n²)

空间负责度 : O(1) ，即在算法运行过程中，只额外使用了常量级的存储空间

2、方法二： 哈希求解法

对于该问题而言，其本质上是一个精确查找问题，而对于精确查找问题来说，时间复杂度最好的数据结构就是哈希表（或散列表），其时间复杂度为 O(1)，那这个问题能否引入哈希表来解决呢？答案是可以的，代码如下：

/**

 

     * 通过使用hashmap+一次遍历获取结果

 

     * @param nums   源数组

 

     * @param target 目标值

 

     * @return

 

     */

 

    public int[] hashFind(int[] nums, int target) {

 

        

 

        Map<Integer, Integer> num2IndexMap = new HashMap<Integer, Integer>();

 

        for(int i=0; i<nums.length; i++) {

 

            // 计算当前数值和目标值之间的差距

 

            int complement = target-nums[i];

 

            // 确认这个差值是否就是我们数组的中一员，如果是，则找到结果

 

            if(num2IndexMap.containsKey(complement)) {

 

                return new int[] {i, num2IndexMap.get(complement)};

 

            }

 

            // 如果没有找到匹配值，则将自己加入到map中，等待其他数值进行匹配

 

            num2IndexMap.put(nums[i], i);

 

        }

 

        

 

        throw new IllegalArgumentException("No Answer!");

 

    }

运行效果图示。

时间复杂度 : O(n) ,  我们只遍历了一遍数据源

空间负责度 : O(n) ，哈希表在最差情况需要将数据源所有数据全部存储一遍