两数之和

一、题目描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

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

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

二、题目分析

给定输入是一个int类型的数组，一个目标值，目标输出是一个int类型的数组，数组中是相加为目标值的数的索引。

三、算法

①暴力解法

 1 public static int[] twoSum1(int[] nums, int target) {
 2     int i;
 3     int j;
 4     for (i = 0; i < nums.length - 1; i++) {
 5         int temp1 = nums[i];
 6         for (j = i + 1; j < nums.length; j++) {
 7             if (nums[j] == target - temp1) {
 8                 return new int[] {i, j};
 9             } else {
10                 continue;
11             }
12         }
13     }
14     return null;
15         
16 }

第一重for循环固定了其中一个加数，第二重for循环用来寻找被加数，如果（目标值 - 加数）== （被加数），那么我们就找到了这两个数，之所以在最外层初始化 i 和 j ，是为了方便定位元素。我最开始还对目标值与加数的大小进行比对，如果加数比目标值大，就跳过本次循环，但是这种情况只在所有元素都为非负的情况下才有用，如果元素为负数就没用了...，所以后面就删掉了。这一种解法因为用到了双重for循环，所以时间复杂度为O（n2），空间复杂度为O（1）。

②使用map

 1 public static int[] twoSum2(int[] nums, int target) {
 2     Map<Integer, Integer> map = new HashMap<Integer, Integer>();
 3     for (int i = 0; i < nums.length; i++) {
 4         map.put(nums[i], i);
 5     }
 6     for (int i = 0; i < nums.length; i++) {
 7         int temp = target - nums[i];
 8         if (map.containsKey(temp) && map.get(temp) != i) {
 9             return new int[] {i, map.get(temp)};
10         }
11     }
12     return null;
13 }

这道题目的核心就是确定一个数之后，在数组中寻找另外一个数及其索引，保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。同样用到了双重for循环，第一重循环把数组中的元素存入ma中，以元素作为key，索引作为value，因为我们想要通过元素得到其对应的索引。第二重for循环首先确定一个加数nums[i]，然后得到了被加数的值，使用map.containsKey()方法来判断map是否存在所要寻找的元素，map.get（temp）!= i 是因为题目要求两个整数，这里过滤掉输入数组中存在相同元素的情况。这种解法时间复杂度为O（n），因为对数组中的 n 个元素进行了循环，空间复杂度为O（n），因为使用了map来保存数组中的 n 个元素。

③一次循环

 1 public static int[] twoSum3(int[] nums, int target) {
 2     Map<Integer, Integer> map = new HashMap<Integer, Integer>();
 3     for (int i = 0; i < nums.length; i++) {
 4         int temp = target - nums[i];
 5         if (map.containsKey(temp)) {
 6             return new int[] {i, map.get(temp)};
 7         }
 8         map.put(nums[i], i);
 9     }
10     return null;
11 }

首先确定加数nums[i]，得到了被加数，在将数组中的元素插入map时先判断map是否已存在所寻找的值，如果有那就直接返回，没有再把它存入map，时间复杂度为O（n），空间复杂度为O（n）。

四、说明

解法均是在我的理解下给出，有参考官方解答。

代码已上传github：

https://github.com/Thinker-Mars/ByteDance/tree/master/sumOfTwoNumbers

来源：力扣（LeetCode）