0%

LeetCode数字之和

两数之和 Two Sum

1
2
3
4
5
6
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

在第一次迭代中,我们将每个元素的值和它的索引添加到表中。
然后,在第二次迭代中,我们将检查每个元素所对应的目标元素(target - nums[i])是否存在于表中。
注意,该目标元素不能是 nums[i]nums[i] 本身!

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

三数之和

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
31
32
33
34
35
36
37
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
// 排序数组
Arrays.sort(nums);
// 固定指针k
for (int k = 0; k < nums.length - 2; k++) {
int j = nums.length - 1;
int i = k + 1;
// 当 nums[k] > 0 时直接break跳出:因为 nums[j] >= nums[i] >= nums[k] > 0,即 33 个数字都大于 00 ,在此固定指针 k 之后不可能再找到结果了。
if (nums[k] > 0) {
break;
}
// 当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]:因为已经将 nums[k - 1] 的所有组合加入到结果中,本次双指针搜索只会得到重复组合。
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
while (i < j) {
int s = nums[i] + nums[k] + nums[j];
if (s == 0) {
ArrayList<Integer> temp = new ArrayList<>();
System.out.println("" + i + j + k);
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
result.add(temp);
i++;
j--;
} else if (s < 0) {
i++;
} else {
j--;
}
}

}
return new ArrayList<>(result);
}

最接近的三数之和

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 int threeSumClosest(int[] nums, int target) {
int min = Integer.MAX_VALUE;
int result = 0;
Arrays.sort(nums);

// 固定指针k
for (int k = 0; k < nums.length; k++) {
int leftLink = k + 1;
int rightLink = nums.length - 1;

while (leftLink < rightLink) {
// 三个数相加必须最接近target
int sum = nums[leftLink] + nums[rightLink] + nums[k];
int offset = Math.abs(target - sum);

if (offset <= min) {
result = sum;
min = offset;
}
if (sum > target) {
rightLink--;
} else {
leftLink++;
}

}
}
return result;
}

四数之和

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
if (nums.length < 4) {
return result;
}
int size = nums.length;
for (int i = 0; i < size - 3; i++) {
// 排序后,如果相邻两数相同,则第二个数运算的结果,是第一个数运算结果的一个子集,可以排除
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 如果四个数之和已经大于目标值,后面永远是不可能有解的
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
// 当前数和后面最大的数相加都比目标值小,直接进入下一次循环
if (nums[i] + nums[size - 1] + nums[size - 2] + nums[size - 3] < target) {
continue;
}
for (int j = i + 1; j < size - 2; j++) {
//去重
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int leftLink = j + 1;
int rightLink = size - 1;
while (leftLink < rightLink) {
int sum = nums[leftLink] + nums[rightLink] + nums[i] + nums[j];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[leftLink], nums[rightLink]));
while (leftLink < rightLink && nums[rightLink] == nums[--rightLink]) ;
while (leftLink < rightLink && nums[leftLink] == nums[++leftLink]) ;

} else if (sum > target) {
// 右指针向左移动
while (leftLink < rightLink && nums[rightLink] == nums[--rightLink]) ;

} else {
// 左指针向右移动
while (leftLink < rightLink && nums[leftLink] == nums[++leftLink]) ;
}
}

}
}
return result;

}