1、两数之和，
题目：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
答案：
1）暴力破解，遍历每个元素 x，并查找后面是否存在一个值与 target−x 相等的目标元素。缺点：时间复杂度高
![]()
1 class Solution {
2 public int[] twoSum(
int[] nums,
int target) {
3 for (
int i = 0; i < nums.length; i++
) {
4 for (
int j = i + 1; j < nums.length; j++
) {
5 if (nums[j] == target -
nums[i]) {
6 return new int[] { i, j };
7 }
8 }
9 }
10 throw new IllegalArgumentException("No two sum solution"
);
11 }
12 }
View Code
2）通过循环遍历两次哈希表，第一次添加全部元素，第二次通过减去元素，查找另外一个是否在哈希表里面。
![]()
1 class Solution {
2 public int[] twoSum(
int[] nums,
int target) {
3 Map<Integer, Integer> map =
new HashMap<>
();
4 for (
int i = 0; i < nums.length; i++
) {
5 map.put(nums[i], i);
6 }
7 for (
int i = 0; i < nums.length; i++
) {
8 int complement = target -
nums[i];
9 if (map.containsKey(complement) && map.get(complement) !=
i) {
10 return new int[] { i, map.get(complement) };
11 }
12 }
13 throw new IllegalArgumentException("No two sum solution"
);
14 }
15 }
View Code
3）循环遍历一次哈希表，每插入一个元素，查看哈希表里面是否含有目标元素，及是否含有target-x，具体上代码：
![]()
1 class Solution {
2 public int[] twoSum(
int[] nums,
int target) {
3 Map<Integer, Integer> map =
new HashMap<>
();
4 for (
int i = 0; i < nums.length; i++
) {
5 int complement = target -
nums[i];
6 if (map.containsKey(complement)) {
7 return new int[] { map.get(complement), i };
8 }
9 map.put(nums[i], i);
10 }
11 throw new IllegalArgumentException("No two sum solution"
);
12 }
13 }
View Code
用户点评