欢迎跟着夏老师一起学习算法，这方面我自己的基础很薄弱，所以解题方法和思路也会讲的很”小白“，不需要什么基础就能看懂。

关注公众号可以进行交流和加入微信群，群内定期有系列文章分享噢！

问题

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

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

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

嵌套循环解题法

通过第 1 遍循环可以拿到当前值和剩余值，然后嵌套循环一次，检查剩余值是不是在数组中。

function twoSum(nums, target) {for(let i = 0;i<nums.length;i++) {const current = nums[i]; // 拿到当前值
    const remain = target - current; // 拿到剩余值
    
    for(let j = 1;j<nums.length;j++) {if(nums[j] === remain) {return [i, j];
      }
    }
  }
}

时间复杂度是 O(n^2)

nums 的长度为 n, 嵌套循环的总执行次数是 n*(n-1)，当 n 趋向于无穷大时 n - 1 和 n 没什么区别，忽略

空间复杂度为 O(1)

增加的临时变量有 current, remain, i, j，不会随着 nums 的长度而增加，所以是常量 O(1)

嵌套循环的效率是最低的, 面试的时候就算回答出来被送走的几率也是很大的。

两遍 HashTable 解题法

核心思想是使用一个 HashTable 保存每个值和每个值的位置。

第 1 次循环时构造出 HashTable，键为 nums 数组的元素，值为元素对应的下标

第 2 次循环时获取当前循环的值以及剩余值，如果剩余值的索引不等于当前值的索引，且剩余值也在 HashTable 中，直接从 HashTable 读取出当前值和剩余值的 index 返回。

function twoSum(nums, target) {const hashTable = {};
  // 第 1 次循环
  for(let i = 0;i<nums.length;i++) {hashTable[nums[i]] = i;
  }
  // 第 2 次循环
  for(let i = 0;i<nums.length;i++) {const current = nums[i];
    const remain = target - current;
    if(map[remain] !== undefined && map[remain] !== i) {return [i, map[remain]];
    }
  }
}

时间复杂度为 O(2n) = O(n)

进行了两次循环，理论上是 2 * n 的时间复杂度，但是当 n 趋向于无穷大时，n 和 2n 的差距可以忽略，所以结果是 O(n)

空间复杂度为 O(n)

增加了 HashTable，大小是 nums 的长度 n，所以空间复杂度是 O(n)

该算法利用了 HashTable 的 O(1) 的时间复杂度巧妙地减少了嵌套循环，算法效率提升很大！

一般回答到这里基本就没啥问题了，但是还有一种基于 HashTable 一次循环就能解决问题的方案。

一遍 HashTable 解题法

循环 nums 数组，得到当前值和剩余值，判断剩余值在不在 HashTable，如果在的话，直接返回剩余值的位置和当前值的位置。如果不在则把剩余值插入 HashTable，继续循环。

Q: 为什么先返回的是剩余值的位置而不是当前值的位置？

A: 因为当前值的位置是确定的，所以当前值的位置不在 HashTable 中，但是剩余值可能在前面的循环中插入了 HashTable，是老值，所以先返回。

function twoSum(nums, target) {const hashTable = {};
  
  for(let i = 0;i<nums.length;i++) {const current = nums[i];
    const remain = target - remain;
    if(hashTable[remain] !== undefined) { // 为什么不需要判断位置? 因为当前值的位置根本没插入 HashTable 中，索引不可能重复
      return [hashTable[remain], i];
    }
    hashTable[current] = i; // 插入当前值到 HashTable，下一次循环时这里就成了 "老值"
  }
}

时间复杂度 O(n)

正宗的 O(n), 一次循环解决问题

空间复杂度 O(n)

增加了 HashTable，大小随着 nums 的增大而增大

结尾

两数之和是 leetcode 的第 1 个问题，也是比较简单的一个问题，对算法有畏难情绪的读者可以把心收到肚子里了，跟着夏老师一起学算法！
有疑问的读者可以扫描上方二维码和我沟通。

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

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

示例：

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

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

实现思路：
题目常规解法是 O(n^2) 的暴力解，分析可以发现，利用好 hashMap 就可以用空间换取时间，把时间复杂度降为 O(n)

我的实现：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {const map = new HashMap()
  const numsLen = nums.length
  for (let i = 0; i < numsLen; i++) {const cup = target - nums[i]
    const index = map.find(cup)
    if (index !== -1) return [index, i]
    else map.put(nums[i], i)
  }
    
};

class HashMap {constructor () {this.map = {}
  }
  put (key, value) {this.map[key] = value
  }
  find (key) {return key in this.map ? this.map[key] : -1
  }
}

成绩

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

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

示例:

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

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

方法 1，暴力解法。

直接每一个元素都与自己之前的元素相加看是否有目标值，有就输出。

代码如下：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if nums[i] + nums[j] == target:
                    target_num = [i,j]
                    return target_num
        return None

​

时间消耗和空间消耗如下：

执行用时: 4500 ms, 在 Two Sum 的 Python3 提交中击败了 32.72% 的用户

内存消耗: 7.3 MB, 在 Two Sum 的 Python3 提交中击败了 85.58% 的用户

方法 2，使用 enumerate 函数

查看评论使用 enumerate 函数效率更高。

enumerate 函数可以将一个数组转化为一个 key 从开始，值为数组对应元素的字典。

代码如下：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return None
            d = dict()
        for i,item in enumerate(nums):
            tmp = target – item
            if tmp in d:
                return [i, d[tmp]]
                d[item] = i
        return None

时间消耗和空间消耗如下：

执行用时: 44 ms, 在 Two Sum 的 Python3 提交中击败了 99.77% 的用户

内存消耗: 7.9 MB, 在 Two Sum 的 Python3 提交中击败了 46.97% 的用户

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

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

<!–more–>

我的垃圾思路

One

1. 我能想到的只有一个循环去遍历每个数字，一个循环去匹配是否有符合的 — O(n^2)
2. 首先想到暴力破解，两个 for 循环去找哪两个索引对应的值加起来等于target(当然这估计过不了关)
3. 但是想到了 HashMap 有个 get 方法效率很高，那么首先把数组中所有元素 put 到map中，将 target - nums[i] 作为 key，索引 index 作为value，那么再写一个循环去遍历数组时候，判断起来就很方便了。
4. 直接用 map.get(nums[i])，即可拿到对应的value，当value 不为 null 的时候证明满足了nums[i] + nums[j] = target, 也就是nums[i] = target - nums[j]。如上面示例的话，map 中会存放的是map:{7:0, 2:1, -2:2, -6:3}
5. 然后再写一个循环去判断 int b = map.get(nums[i])不为空 且 b != i 时 <font color=grey size=2>(因为当 nums[0]==3，target==6 就会得到 [0,0]，很显然这是错误的，题目中提到了不能重复利用这个数组中同样的元素)</font>，即可break，[i,b] 就是答案

Two

1. 不过还是写个两个循环，能否写成一个循环呢？（根据提交的答案结果看来，两者差距不大）

1. 那就是一个循环，边循环，边 put 到map中（key,value同上），循环过程中再去判断是否 map 已经 contains 这个 nums[i] 了，如果包含则满足了nums[i] = target - nums[j]，即可以break

上面都将 $ O(n^2)->O(n) $

我的垃圾代码

package com.dasnnj.practice.simple;

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

/**
 * Description <p> TODO:
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。* 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。* <p>
 * 示例:
 * <p>
 * 给定 nums = [2, 7, 11, 15], target = 9
 * <p>
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]</p>
 *
 * @author DASNNJ <a href="mailto:dasnnj@outlook.com"> dasnnj@outlook.com </a>
 * @date 2019-04-28 15:38
 */
public class TwoSum {static int[] twoSum(int[] nums, int target) {
        //One
        /*//key 为 target-nums[i],value 为 index
        Map<Integer, Integer> map = new HashMap<>();
         for (int i = 0; i < nums.length; i++) {map.put(target-nums[i],i);
         }
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            Integer b;
            if ((b = map.get(nums[i])) != null && b != i) {res[0] = b;
                res[1] = i;
                break;
            }
        }
        return res;
        */
        //Two
        //key 为 target-nums[i],value 为 index
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {if (map.containsKey(nums[i])) {res[0] = map.get(nums[i]);
                res[1] = i;
                break;
            }
            map.put(target - nums[i], i);
        }
        return res;
    }

    public static void main(String[] args) {int[] nums = new int[]{2, 7, 11, 15};
        System.out.println(Arrays.toString(TwoSum.twoSum(nums, 9)));
    }
}