上一篇相关文章：【力扣刷题】Day05——哈希表专题_塔塔开!!!的博客-CSDN博客
5. 四数相加
题目链接：454. 四数相加 II - 力扣（LeetCode）
思路一：四重循环暴力枚举——超时
Code
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int cnt = 0;
for(int i = 0; i < nums1.length; i ++){
for(int j = 0; j < nums2.length; j ++){
for(int k = 0; k < nums3.length; k ++){
for(int l = 0; l < nums4.length; l ++){
if(nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0){
cnt ++;
}
}
}
}
}
return cnt;
}
}
思路二：两重循环枚举 + 哈希表，分组枚举，将四重循环优化到两重
a + b + c + d = 0
- 循环枚举
nums1，nums2将a + b存入哈希表并统计次数，mp<a+b, cnt> - 枚举
nums3 nums4进行判断，由a + b + c + d = 0即a+b = 0 - (c+d)，若先前nums1 nums2存在a+b使得a+b == -(c+d)即说明a + b + c + d = 0（判断某个集合中的元素是否出现过——哈希表），那么答案cnt += value
之所以要哈希表要记录a+b的次数，是因为有多种结果，方便我们统计答案：
nums1[x1] + nums2[x2] = 5
nums1[x3] + nums2[x4] = 5
当枚举nums3 nums4时，若nums3[x5] + nums4[x6] = -5，那么本次就用两种答案：
这样时间复杂度就从(n^4) --> 2次(n^2)
Code
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> mp = new HashMap<>();
for(int a : nums1){
for(int b : nums2){
mp.put(a + b, mp.getOrDefault(a + b, 0) + 1);
}
}
int cnt = 0;
for(int c : nums3){
for(int d : nums4){
int tmp = 0 - (c + d);
if(mp.containsKey(tmp)){
cnt += mp.get(tmp);
}
}
}
return cnt;
}
}
6. 赎金信
题目链接：383. 赎金信 - 力扣（LeetCode）
思路：哈希表计数
串1能由串2构成：串2中对应串1的字母个数要>=串1的字母个数
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()) return false;
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for(int i = 0;i < ransomNote.length(); i ++) cnt1[ransomNote.charAt(i) - 'a'] ++;
for(int i = 0;i < magazine.length(); i ++) cnt2[magazine.charAt(i) - 'a'] ++;
for(int i = 0;i < ransomNote.length(); i ++){
int idx = ransomNote.charAt(i) - 'a';
if(cnt2[idx] < cnt1[idx])
return false;
}
return true;
}
}
7. 三数之和
题目链接：15. 三数之和 - 力扣（LeetCode）
其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意！
思路：排序 + 循环枚举a , 双指针枚举b 和 c（固定a，双指枚举b c判断和）
- 排序
- 外层枚举
i（a），里边双指针left（i+1开始） right枚举b c，若sum = a+b+c
> 0，那么right --< 0，那么left ++= 0，记录答案
由于结果集不能冲重复，因此要注意去重剪枝，跳过重复的结果集。
对a去重：
if(i > 0 && nums[i] == nums[i - 1]) continue;
为啥不是nums[i] == nums[i + 1]然后continue呢？
- 要是这样的话，有的结果集就直接pass过去了，比如
{-1 - 1 2}，当i在第一个位置，left在2，right在3，nums[i] == nums[i + 1]这个结果直接跳过了
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i ++){
if(nums[i] > 0){
return res;
}
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{
res.add(Arrays.asList(nums[i], 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 res;
}
}
8. 四数之和
题目链接：18. 四数之和 - 力扣（LeetCode）
思路：和三数之和一样的解题思路，只不过多了一层循环，固定枚举a b，双指针枚举c d，由于target是任意的因此要额外注意剪枝的细节，同时结果集不能重复，因此也要对a b c d进行去重操作！！
剪枝：
if(nums[k] > target && nums[k] >= 0){
break;
}
if(nums[i] + nums[k] > target && nums[i] + nums[k] >= 0){
break;
}
Code
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int k = 0; k < nums.length; k ++){
if(nums[k] > target && nums[k] >= 0){
break;
}
if(k > 0 && nums[k] == nums[k - 1]){
continue;
}
for(int i = k + 1; i < nums.length; i ++){
if(nums[i] + nums[k] > target && nums[i] + nums[k] >= 0){
break;
}
if(i > k + 1 && nums[i] == nums[i - 1]){
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(left < right){
long sum = (long)(nums[k] + nums[i] + nums[left] + nums[right]);
if(sum < target) left ++;
else if(sum > target) right --;
else {
res.add(Arrays.asList(nums[k] , nums[i] , 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 res;
}
}
|