1、两数之和

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

1
2
3
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/two-sum

1、暴力解

暴力解,没什么说的,两层循环,每两个数相加判断是否等于target。

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

2、一遍哈希表(官方解法)

这个方法本质上是:拟定数组的当前下标的值为两数之中的一个数,然后去找另一个数,如果找不到则下一个数继续这么找,直到最后。

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}

3、数组解法

数组为排序数组从两边同时遍历数组,两数加和判断是否为target,如果小于target,则头指针加1,如果大于target尾指针加1,直到两指针相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int[] twoSum(int[] nums, int target) {
int[] result = {0, 0};
int a;
int i = 0, j = nums.length - 1;
while (i < j) {
a = nums[i] + nums[j];
if (a == target) {
result[0] = i;
result[1] = j;
} else if (a > target) {
j--;
} else {
i++;
}
}
return result;
}