两数之和

##两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

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

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

使用hashmap将数组中的值作为key,下标作为value值放入map中,查的时候只找map中是否有target-nums[i],则返回的就是i和target-nums[i]的下标。

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

返回两个数的值
指针i指向数组的头,而j指向屁股,然后直到他俩相遇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static int[] twoSum(int[] nums, int target) {
if (nums == null) {
return null;
}
int i = 0;
int j = nums.length - 1;
ArrayList<Integer> list = new ArrayList<>();
Arrays.sort(nums);
for (int x = 0; x < nums.length; x++) {
while (i < x && j > x) {
if (Math.abs(i - j) == 1) {
break;
}
if (j >= 0 && target < nums[j]) {
j--;
}
if (i < nums.length && j >= 0 && nums[i] + nums[j] == target) {
list.add(nums[i]);
i++;
list.add(nums[j]);
j--;
}
}
}
int[] re = new int[list.size()];
for (int i1 = 0; i1 < re.length; i1++) {
re[i1] = list.get(i1);
}
return re;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (nums []int, target int) []int {
if nums==nil {
return nil
}
m:=make(map[int]int)

for i:=0;i<len(nums) ;i++ {
captial,ok:=m[target-nums[i]]
if ok{
s:=[] int{captial,i}
return s
}else {
m[nums[i]]=i
}
}
return nil

}