代码随想录算法训练营第六天-454四数相加II、383赎金信、15三数之和、18四数之和
初步题解
454 四数相加 II
题目链接：(https://leetcode.cn/problems/4sum-ii/)
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 class LE454 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] nums1 = Arrays.stream(scanner.nextLine().split(",")).filter(Objects::nonNull).mapToInt(Integer::parseInt).toArray();
int[] nums2 = Arrays.stream(scanner.nextLine().split(",")).filter(Objects::nonNull).mapToInt(Integer::parseInt).toArray();
int[] nums3 = Arrays.stream(scanner.nextLine().split(",")).filter(Objects::nonNull).mapToInt(Integer::parseInt).toArray();
int[] nums4 = Arrays.stream(scanner.nextLine().split(",")).filter(Objects::nonNull).mapToInt(Integer::parseInt).toArray();
System.out.println(fourSumCount(nums1, nums2, nums3, nums4));
}
public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap();
for (int k : nums1) {
for (int i : nums2) {
int sum = k + i;
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
for (int i : nums3) {
for (int j : nums4) {
res += map.getOrDefault(-i - j, 0);
}
}
return res;
}
}
|
383 赎金信
题目链接：(https://leetcode.cn/problems/ransom-note/submissions/534463469/)
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
| public class LE383 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String ransomNote = scanner.nextLine();
String magazine = scanner.nextLine();
System.out.println(canConstruct(ransomNote, magazine));
}
public static boolean canConstruct(String ransomNote, String magazine) {
int[] ints = new int[26];
for (int i = 0; i < magazine.length(); i++) {
ints[magazine.charAt(i) - 97]++;
}
for (int i = 0; i < ransomNote.length(); i++) {
ints[ransomNote.charAt(i) - 97]--;
}
for (int i : ints) {
if (i < 0) {
return false;
}
}
return true;
}
}
|
15 三数之和
题目链接：(https://leetcode.cn/problems/3sum/description/)
暴力解法，但是这样超时了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public static List<List<Integer>> threeSum(int[] nums) {
HashMap<String, List<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
list.sort(Integer::compareTo);
map.put(list.stream().map(integer -> integer + "").collect(Collectors.joining(",")), list);
}
}
}
}
List<List<Integer>> list = new ArrayList<>();
for (Map.Entry<String, List<Integer>> stringListEntry : map.entrySet()) {
list.add(stringListEntry.getValue());
}
return list;
}
|
看了部分解析改用双指针，可以通过，但是比较慢。而且费时
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
| public static List<List<Integer>> threeSum(int[] nums) {
nums = Arrays.stream(nums).sorted().toArray();
ArrayList<List<Integer>> list = new ArrayList<>();
if (nums[0] + nums[1] + nums[2] > 0) {
return list;
}
int i = 0;
int j = i + 1;
int k = nums.length - 1;
while (i < j && j < k) {
System.out.println(i + " " + j + " " + k);
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
list.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
} else if (sum < 0) {
j++;
} else {
k--;
}
while (j > i + 1 && j <= nums.length - 1 && nums[j] == nums[j - 1]) {
j++;
}
while (k > j && k != nums.length - 1 && nums[k] == nums[k + 1]) {
k--;
}
if (j >= k) {
i = i + 1;
while (i != 0 && i <= nums.length - 1 && nums[i] == nums[i - 1]) {
i++;
}
j = i + 1;
k = nums.length - 1;
}
}
return list;
}
|
18 四数之和
题目链接：(https://leetcode.cn/problems/4sum/description/)
看到题目，就觉得是 15 的进阶版，按照上一题的思路写了一下
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
| public static List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
ArrayList<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
long sum = (long) nums[i] + (long) nums[j] + (long) nums[left] + (long) nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
list.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
}
return list;
}
|
看讲解
454 四数相加 II
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0454.四数相加II.html)
383 赎金信
题目链接/文章讲解：(https://programmercarl.com/0383.赎金信.html)
15 三数之和
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0015.三数之和.html)
确实用 for 循环更好理解。题解的思路更加清晰，而且更快。
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
| public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (right > left) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (right > left && nums[right] == nums[right - 1]) {
right--;
}
while (right > left && nums[left] == nums[left + 1]) {
left++;
}
right--;
left++;
}
}
}
return result;
}
|
18 四数之和
题目链接/文章讲解/视频讲解：(https://programmercarl.com/0018.四数之和.html)
看了解析。加上剪枝操作。
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
| public static List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
ArrayList<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0 && nums[i] > target) {
return list;
}
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] > 0 && nums[i] + nums[j] > target) {
break;
}
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
long sum = (long) nums[i] + (long) nums[j] + (long) nums[left] + (long) nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
list.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
}
return list;
}
|