454. 四数相加II
哈希表中的经典题目。因为不需要考虑去重的操作，所以和四数之和不一样。
解题思路：
- 为什么想到哈希法？
在集合中判断一个元素有没有出现过 - 大致思路：遍历AB数数组，把a+b放入一个集合，再遍历CD数组，看其中是否有匹配项。
- 使用的数据结构：数据很大所以不能是数组，所以只能是set或map，因为不仅要统计是否出现过，还要统计出现的次数，所以使用map。
解题步骤：
- 定义int res = 0; Map<Integer, Integer> map = new HashMap<Integer, Integer>();
- 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
- 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。注意，count应该+value所存的值。
- 返回res。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
for(int i : nums1){ // 注意这里增强for循环
for(int j : nums2){
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0)+1); //注意map.getOrDefault
}
}
for(int i : nums3){
for(int j : nums4){
int sum1 = i + j;
res += map.getOrDefault(0-sum1, 0);
}
}
return res;
}
}
map.getOrDefault(sum, 0)
这是 Map 接口提供的一个默认方法。
它尝试获取键 sum 对应的值。可以简单理解为统计次数。
如果 sum 在 map 中存在，则返回对应的值。
如果 sum 不存在，则返回默认值 0。
383. 赎金信
思路和242. Valid Anagram一致
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()){
return false;
}
int[] record = new int[26];
for(int i = 0; i < magazine.length(); i++){
record[magazine.charAt(i)-'a']++;
}
for(int j = 0; j < ransomNote.length(); j++){
record[ransomNote.charAt(j) - 'a']--;
if(record[ransomNote.charAt(j) - 'a'] < 0){
return false;
}
}
return true;
}
}
15. 三数之和
用哈希法去重太复杂了，所以使用双指针。
解题思路：
这道题使用双指针法一定要排序。
大题思路如下
思路
这道题的细节在于去重，因为结果集中不能有重复：
伪代码
//定义二维数组存放结果集
List<List<Integer>> result = new ArrayList<>();
//对数组排序
Arrays.sort(nums);
//遍历数组
for(int i = 0; i < nums.length; i++){
//如果nums[i]>0，可以直接return
if(nums[i] > 0){
return result;
}
//第一步去重 -> 对a进行去重
//因为要判断i-1，所以i > 0，防止数组下标越界
if(i > 0 && nums[i] == nums[i-1]){
continue;
}
//获取b，c的值
int left = i + 1;
int right = nums.length - 1;
//移动left和right指针
while(right > left){ //边界调节代入，当left == right是否合法？-> 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]));
//对b，c进行去重，这里相当于跳过相同的元素
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
//anyway要移动指针
right--;
left++;
}
}
}
去重的细节：
- 是判断nums[i] == nums[i+1] 还是nums[i] == num[i - 1]?
可以理解为i+1实际上是left，如果是nums[i] == nums[i+1]，就成了判断结果集中有没有重复的元素，所以应该是nums[i] == num[i - 1]，看前面有没有出现过相同元素。 - 移动left和right指针时 while(right > left)，去重的逻辑一定要放在收获结果之后
代码实现的记录
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; //注意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])); //注意Arrays.asList方法
while(right > left && nums[right] == nums[right - 1]) right--;
while(right > left && nums[left] == nums[left + 1]) left++; //注意这里是nums[left + 1])
right--;
left++;
}
}
}
return result;
}
}
Arrays.asList 方法是 Java 标准库中的一个静态方法，用于将一个数组转换为一个固定大小的 List。这个方法常用于将数组快速转换为 List 以利用集合框架提供的功能。需要注意的是，这个 List 是一个视图，它是基于原始数组的，因此不能调整大小，但可以更改元素。
18. 四数之和
思路
整体思路还是nums[i] + nums[k] + nums[left] + nums[right] = 0;
需要注意的细节：
- 剪枝和去重
- 不能判断nums[k] > target 就返回了，因为三数之和中，0是确定的数，而target并不确定。
所以剪枝应该
if (nums[k] > target && nums[k] >= 0) {
break; // 这里使用break，统一通过最后的return返回
}
- 去重
// 对nums[k]去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
- 遍历到i也需要进行剪枝和去重：
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
// 对nums[i]去重
//i > k + 1 因为i是从k+1开始的
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
代码实现细节：
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 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(right > left){
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; //注意这里是long，并且要放在while循环内
if(sum > target){
right--;
}else if(sum < target){
left++;
}else{
result.add(Arrays.asList(nums[i], nums[j], 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;
}
}
