Day7:(哈希表)|454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

454.四数相加II

• 题目链接：第454题.四数相加II
• 解题思路：本体考察对哈希表map结构的应用。要求从四个数组里找四个数使其和为0，这里使用两两求和的方式，每次循环遍历两个数组。
• 主要难点：map的应用，key和value分别代表什么（key是两两的和，value是这个值出现的次数）每次两个数组求和，两两比较的思想
• 解题步骤：
  • 首先选两个数组进行求和，把求和的数在map中比较，如果没出现过就放进去，value设置为1，如果出现过则放进去，value设为当前value+1，value表示这个值的出现次数。
  • 接下来遍历剩下的两个数组进行求和，现在找的是这两个数的和和前面两个数的和的总和为0的数。如果找到了，则使得最终结果res加上这个满足条件值的value,也就是出现的次数。
  • 返回res
• 解题时间：25+5
• 代码：

class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
int a;
int res = 0;
for(int i:nums1){
for(int j:nums2){
a = i+j;
if(map.containsKey(a)){
map.put(a,map.get(a)+1);//map里出现过a这个值了，把它对应的出现次数加1.
}else{
map.put(a,1);//map中还没有出现过a这个值，将其加入map，value出现次数设置为1
}
}
}
for(int i:nums3){
for(int j:nums4){
a = i+j;
if(map.containsKey(0-a)){
res += map.get(0-a);
}
}
}
return res;
}
}

383. 赎金信

• 题目链接：383. 赎金信
• 解题思路：和昨天的“字母异位词”思路差不多，都是用数组模拟哈希表。
• 主要难点：用数组模拟哈希表，为什么不用map？
• 解题步骤：
  • 首先新建一个长度为26的数组来模拟哈希表用来储存每个字母出现的次数
  • 先遍历长的单词magazine，其中字母每出现一次使哈希表对应字母的位置+1
  • 再遍历短的单词ransomNote，其中字母每出现一次使哈希表对应字母的位置-1
  • 最后遍历哈希表，如果有某个字母的值为负数，则说明不能满足题目要求。
• 解题时间：15+5
• 代码：

class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] record = new int[26];
for(char c:magazine.toCharArray()){
record[c-'a']+=1;
}
for(char c:ransomNote.toCharArray()){
record[c-'a']-=1;
}
for(int i:record){
if(i<0){
return false;
}
}
return true;
}
}

15. 三数之和

• 题目链接：15. 三数之和
• 解题思路：一开始想着用哈希表解决，但是没思路，看了解析之后决定用双指针法去做。
• 主要难点：双指针法，提前排序，去重逻辑
• 解题步骤：
  • 首先将整个数组进行升序排序，然后从头开始循环，在后面部分的头尾设立双指针
  • 当三者之和大于0时，应该将右指针向左移，反之同理
  • 进行去重操作
• 解题时间：30+5
• 代码：

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);//先对nums排个序，升序
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
return result;//排完序之后第一个元素都大于0，肯定没有满足情况的了
}
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int left = i+1;
int right = nums.length-1;
while(right>left){
if(nums[i]+nums[left]+nums[right]>0){
right--;
}else if(nums[i]+nums[left]+nums[right]<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. 四数之和

• 题目链接：18. 四数之和

• 解题思路：和上一道题三数之和差不多，改成两层循环套双指针，剪枝上一些细节地方要注意

• 主要难点：各种情况的逻辑确定

• 解题时间：30+3

• 代码：

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 - 1] == nums[i]) {
// 对nums[i]去重
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j - 1] == nums[j]) {
// 对nums[j]去重
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (right > left) {
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]));
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return result;
}
}

总结

• 今天四道题主要都是用哈希表匹配的，和昨天的字母异位词那道题差不多。

最后

以上就是贤惠冰棍为你收集整理的Day7:(哈希表)|454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和的全部内容，希望文章能够帮你解决Day7:(哈希表)|454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。