454 四数相加II
https://leetcode.com/problems/4sum-ii/description/
HashMap 统计前两个数组所有变量之和 并统计次数
比较后两个数组所有变量之和 是否存在 存在即+1
就可以得到总数量
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
| class Solution{
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4){
Map<Integer, Integer> map = new HashMap<>();
int result = 0;
for (int i : nums1){
for (int j : nums2){
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
for (int i : nums3){
for (int j : nums4){
int sum = i + j;
result += map.getOrDefault(-sum, 0);
}
}
return result;
}
}
|
383 赎金信
https://leetcode.com/problems/ransom-note/submissions/1133507064/
本质上就是242 有效的字母异位词
把magazine里面的字母记录进array哈希表里面
之后对比magazine 哈希表里面的数值和ransomNote, 如果有负数，说明用超了，return false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public boolean canConstruct(String ransomNote, String magazine){
int[] mag = new int[26];
for(int i = 0; i < magazine.length(); i++){
mag[magazine.charAt(i) - 'a']++;
}
for(int i = 0; i < ransomNote.length(); i++){
mag[ransomNote.charAt(i) - 'a']--;
}
for(int i : mag){
if (i < 0){
return false;
}
}
return true;
}
}
|
15 三数之和
- 哈希法可以做，但不好去重，因为去重操作繁琐
- 双指针可解
把数组排序后， 进行操作
设置i在0位置，left在i+1位置，right在数组最后
如果i+left+right > 0, right–;
i+left+right = 0, left++
i+left+right < 0, left++;
需要考虑a,b,c的去重
因为数据不能重复
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
| class Solution{
public 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 (left < right){
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 四数之和
逻辑上和三数之和一个思路，使用双指针
在三数之和上套一层for循环
比454 四数相加II 难，因为是在同数组下进行查找，并且需要去重
四数相加逻辑是在原来的nums[i]的基础上再套一层nums[k]进行计算
那么5数之和，6数之和同一个逻辑
与三数之和不同的剪支，在一层逻辑上是与三数之和的0不同，因为负值相加会更小，所以只适用于正数
一定要注意要先整理数组nums
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
| 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] > 0 && nums[i] > target){
return result;
}
if (i > 0 && nums[i] == nums[i-1]){
continue;
}
for (int k = i + 1; k < nums.length; k++){
if (k > i + 1 && nums[k] == nums[k-1]){
continue;
}
int left = k+1;
int right = nums.length - 1;
while (left < right){
int sum = nums[i] + nums[k] + nums[left] + nums[right];
if (sum > target){
right--;
} else if (sum < target){
left++;
} else {
result.add(Arrays.asList(nums[i],nums[k],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;
}
}
|