力扣01 求两数之和

力扣01 求两数之和

题目：

给定一个整数数组，返回两个数字的索引，使它们加起来为一个特定的目标。

您可以假设每个输入只有一个解决方案，并且您可能不会两次使用同一个元素。

示例：

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

注：题目大意就是在给定的一个数组中找到两个数组元素之和为给定的target并且返回这两个数组元素在数组中的下标。

解法一：暴力求解

解题思路：

依次固定数组的第一个元素，并开始遍历数组（从固定元素的下一个元素开始）看其他元素与固定元素加起来是否等于target若等于则返回这两个数组的下标若不等于则重复此操作。

代码：

/**
 * 暴力解决：每次固定一个数再遍历剩余数组中的元素看这两个数之和是否等于target
 * 如果等于就返回这两个数在数组中所对应的下标值
 */
public class TowSum01 {
        /**
         * 定义一个方法返回类型为一个数组，参数为指定的一个数组以及目标值
         * 返回的数组元素为对应两个目标数在原来数组中的下标值
         * @param nums
         * @param target
         * @return
         */
        public int[] towSum ( int[] nums, int target){
            //1.定义一个长度为2的数组用以存储目标数在原来数组中的下标值
            int[] result = new int[2];
            //2.第一层循环是固定原来数组的元素因为每一个都要固定一次
            for (int i = 0; i < nums.length; i++) {
                //2.1第二层循环是寻找剩下元素是否有元素与固定的元素加起来值为target
                for (int j = i + 1; j < nums.length; j++) {
                    //2.2将固定元素与剩下的元素加起来看值是否等于target
                    int sum = nums[i] + nums[j];
                    if (sum == target) {
                        //2.3如果sum等于target则将这两个元素的下标放在result数组中并返回result
                        result[0] = i;
                        result[1] = j;
                        return result;
                    }
                }
            }
            return result;
        }
}

解法二：哈希表求解

解题思路：

使用哈希表求解，将原本数组中的元素作为哈希表中的key将数组元素对应的数组下标作为哈希表中的value，并按照此规则将数组放进哈希表中。遍历此哈希表用target-key的值作为参照并在哈希表中查找是否有符合此值的key，若存在符合此值的key则返回此key的value。

代码：

import java.util.Hashtable;

/**
 * 使用哈希表法：将原本数组中的元素作为哈希表中的key将原本数组中元素的下标作为哈希表中的value
 * 遍历一次原来的数组将按照以上规则放进哈希表中
 * 使用target-key看差值在哈希表中是否存在若存在则返回value
 */
public class TowSum02 {
    //1.定义一个方法，返回值类型为长度为2的数组，参数为一个数组以及int类型的target
    public int[] towSum(int[] nums,int target){
        //2.定义一个长度为2的数组用来存储返回的两个value
        int[] result = new int[2];
        //3.定义一个哈希表用来存储元本数组的元素以及对应元素的下标值
        Hashtable<Integer, Integer> map = new Hashtable<>();
        //4.遍历原本的数组将元素作为key将下标作为value存储在map中
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],i);
        }
        //5.遍历数组元素并用target与数组元素做差看其差值是否在map中
        for (int j = 0; j < nums.length; j++) {
            //5.1 target与数组元素做差
            int diff = target - nums[j];
            //5.2 看差值是否在map中且不能是同一个元素
            if(map.containsKey(diff) && map.get(diff) != j){
                //6.将数组的下标值以及map中找到对应key的value（也就是另一个下标值）放进result中
                result[0] = j;
                result[1] = map.get(diff);
                return result;
            }
        }
        return result;
    }
}

总结： 解法一的时间复杂度为O(N²)，解法二的时间复杂度为O(N)。