训练营Day7
几把公司,提了辞职之后更忙了。好多好多天没有打卡了
# 454.四数相加 (opens new window)
可以使用四套for循环暴力解法。但是这样时间复杂度就是O(n^4)
可以先计算前两行的数字。计算他们两两相加的和,并且计算和的出现次数
然后再计算后两行数字,计算他们的两两相加。0减去他们的和是否在上一轮的结果中出现,如果出现了,result就加上上轮结果的次数。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
int temp = nums1[i] + nums2[j];
if (!map.containsKey(temp)){
map.put(temp,1);
}else {
map.put(temp, map.get(temp)+1);
}
}
}
int result = 0;
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
int temp = nums3[i]+nums4[j];
if (map.containsKey(0-temp)){
result+= map.get(0-temp);
}
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 383.赎金信 (opens new window)
简单题目,直接上答案
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr = new int[26];
for (int i = 0; i < magazine.length(); i++) {
arr[magazine.charAt(i)-'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
arr[ransomNote.charAt(i)-'a']--;
}
for (int i = 0; i < arr.length; i++) {
if (arr[i]<0){
return false;
}
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 15.三数之和 (opens new window)
这题难一些。网上的说法是先排序,然后用双指针去算。比较难理解的地方在于如何去重
去重逻辑是,i的去重,是与指针反方向对比,left和right和指针方向对比。
为什么这么理解呢,因为i是需要固定的,如果它一直往前移动,就可能和left重合,就相当于判断元组内不允许重复元素。
right和left为什么是向指针移动方向去重呢?是因为结果已经放进去集合里面。如果不往指针方向移动,下一次还是会添加这个结果。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
//循环i
for(int i = 0;i<nums.length;i++){
//如果最左边的值大于0了,就可以直接返回
if(nums[i]>0){
return result;
}
if(i>0&&nums[i]==nums[i-1]){ //去重i
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;
}
}
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
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
# 18.四数之和 (opens new window)
其基本原理就是和上个题目一样,只需要多家一层for循环。
//给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[
//b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):
//
//
// 0 <= a, b, c, d < n
// a、b、c 和 d 互不相同
// nums[a] + nums[b] + nums[c] + nums[d] == target
//
//
// 你可以按 任意顺序 返回答案 。
//
//
//
// 示例 1:
//
//
//输入:nums = [1,0,-1,0,-2,2], target = 0
//输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
//
//
// 示例 2:
//
//
//输入:nums = [2,2,2,2,2], target = 8
//输出:[[2,2,2,2]]
//
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 200
// -10⁹ <= nums[i] <= 10⁹
// -10⁹ <= target <= 10⁹
//
//
// Related Topics 数组 双指针 排序 👍 1613 👎 0
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//剪枝
if (nums[i] > target && (nums[i] >= 0 || target >= 0)) {
return result;
}
//去重
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
for (int j = i+1; j < nums.length; j++) {
//去重
if (j > i+1 && nums[j - 1] == nums[j]) {
continue;
}
int left = j + 1;
int right = nums.length-1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
//加到结果
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
//按照指针的方向去去重
while (left < right && nums[right] == nums[right-1]) right--;
while (left < right && nums[left] == nums[left+1]) left++;
//去重之后,继续移动
left++;
right--;
}
}
}
}
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
上次更新: 2023/06/19, 18:58:48