代码随想录 Day7
今日任务
454.四数相加Ⅱ
383.赎金信
15.三数之和
18.四数之和
454. 四数相加Ⅱ
考点：哈希表
链接：https://leetcode.cn/problems/4sum-ii/
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
int count = 0;
for(int i = 0; i < nums1.length; i++){
for(int j = 0; j < nums2.length; j++){
int sum = nums1[i] + nums2[j];
if(record.containsKey(sum)){
record.put(sum, record.get(sum) + 1);
}
else{
record.put(sum, 1);
}
}
}
for(int i = 0; i < nums3.length; i++){
for(int j = 0; j < nums4.length; j++){
int sum = nums3[i] + nums4[j];
int target = 0 - sum;
if(record.get(target) != null){
count += record.get(target);
}
}
}
return count;
}
}
383. 赎金信
考点：哈希表
链接：https://leetcode.cn/problems/ransom-note/
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] record = new int[26];
for(int i = 0; i < magazine.length(); i++){
record[magazine.charAt(i) - 'a']++;
}
for(int i = 0; i < ransomNote.length(); i++){
record[ransomNote.charAt(i) - 'a']--;
if(record[ransomNote.charAt(i) - 'a'] < 0){
return false;
}
}
return true;
}
}
15. 三数之和
考点：双指针（哈希表麻烦）
链接：https://leetcode.cn/problems/3sum/
解题思路：卡哥视频
注意事项：此题还是有很多细节点的
- 为什么这道题可以先对数组排序再求解？
因为这道题需要我们返回的并不是数组元素的下标，而是数组中的元素，所以可以对数组进行排序，这样哪怕数组元素不在原来的位置也不会影响最终结果； - 为何这道题对 i 去重时要写成
nums[i] == nums[i - 1]而不是nums[i] == nums[i + 1]？
这和我们对 left 的处理有关，因为我们 left 的初始位置是在 i 右侧一个，如果直接判断 nums[i] 和 nums[i + 1] ，相当于我们会忽略掉nums[i] == nums[left]但其实结果符合nums[i] + nums[left] + nums[right] == 0的情况，所以去重时我们要使用nums[i] == nums[i - 1]这种判断方式；同理，后续对 left 和 right 的处理也是一样，left 向右移动，那么想要去重就要和 nums[left + 1] 比较，right 向左移动，想要去重就要和 nums[right - 1] 比较； - 我们需要先将结果加到 result 中，再对 left 和 right 去重，否则会导致result 中一个结果都没有。
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(i > 0 && nums[i] == nums[i - 1]){
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(left < right){
while(left < right && nums[i] + nums[left] + nums[right] > 0){
right--;
}
while(left < right && nums[i] + nums[left] + nums[right] < 0){
left++;
}
if(left < right && nums[i] + nums[left] + nums[right] == 0){
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
// while的时候务必注意下标范围
while(left < right && nums[left] == nums[left + 1]){
left++;
}
while(left < right && nums[right] == nums[right - 1]){
right--;
}
left++;
right--;
}
}
}
return result;
}
}
18. 四数之和
考点：
链接：https://leetcode.cn/problems/4sum/
思考问题：本题和454.四数相加Ⅱ的区别在哪里，为什么四数相加Ⅱ会简单很多？
四数相加Ⅱ是求四个数组之间的元素相加和为0的情况有多少种，哪怕元素值相等，但只要不是同一个数组中同位置的元素，就是不同的结果；但是此题要求元组不能重复；也就是说四数相加Ⅱ中(-1, -1, 1, 1)和(-1, 1, 1, -1)可能是两种结果，但在四数之和中，(-1, -1, 1, 1)和(-1, 1, 1, -1)只能算作一种结果，由去重产生的一系列需要考虑的情况导致了难度的上升。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
//错误的剪枝操作，nums[0]为负数且nums[0]>target是有可能的
// if(nums.length < 4 || nums[0] > target){
// return result;
// }
for(int i = 0; i < nums.length - 3; i++){
//这里的剪枝操作必须是 nums[i]>0 时才可以
//因为在 nums[i]<0 时是有可能通过继续和负数相加得到target的
if(nums[i] > 0 && nums[i] > target){
return result;
}
//这里的if不要写成while，否则continue会死循环
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
for(int j = i + 1; j < nums.length - 2; j ++){
if(j > i + 1 && nums[j] == nums[j - 1]){
continue;
}
int left = j + 1;
int right = nums.length - 1;
while(left < right){
while(left < right && nums[i] + nums[j] + nums[left] + nums[right] > target){
right--;
}
while(left < right && nums[i] + nums[j] + nums[left] + nums[right] < target){
left++;
}
if(left < right && nums[i] + nums[j] + nums[left] + nums[right] == target){
result.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 result;
}
}
因为在三数之和时我没有进行剪枝操作，所以这道题写剪枝的时候就出现了很多意料之外的bug
