My LeetCode Diary - Day7 HashTable
454. 4Sum II
nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Iterated over nums1 and nums2, pairSums = {1 + (-2), 1 + (-1), 2 + (-2), 2 + (-1)} = {-1, 0, 0, 1} pairCountBySum = {-1 : 1, 0 : 2, 1 : 1}, i.e. there is 1 pair with sum = 1, 2 pairs with sum = 0, 1 pair with sum = -1
Iterated over nums3 and nums4, pairSums = {-1 + 0, -1 + 2, 2 + 0, 2 + 2} = {-1, 1, 2, 4} Negate this to be able to find -(c + d) = {1, -1, -2, -4}
Use the hashMap pairCountBySum = {-1 : 1, 0 : 2, 1 : 1} for each item in {1, -1, -2, -4}
fourSumCount = 0 fourSumCount += map.get(1) ⇒ fourSumCount = 0 + 1 = 1 fourSumCount += map.get(-1) ⇒ fourSumCount = 1 + 1 = 2 fourSumCount += map.get(-2) ⇒ fourSumCount = 2 + 0 = 2 fourSumCount += map.get(-4) ⇒ fourSumCount = 2 + 0 = 2
Number of tuples = 2 [Ans]
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
var pairCountBySum = new HashMap<Integer, Integer>();
for (var num1 : nums1)
for (var num2 : nums2)
pairCountBySum.compute(num1 + num2, (k, sumCount) -> sumCount == null ? 1 : ++sumCount);
var fourSumCount = 0;
for (var num3 : nums3)
for (var num4 : nums4)
fourSumCount += pairCountBySum.getOrDefault(-(num3 + num4), 0);
return fourSumCount;
}
383. Ransom Note
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> result = new HashMap<>();
for(char c : ransomNote.toCharArray()){
result.put(c,result.getOrDefault(c,0)+1);
}
for(char c : magazine.toCharArray()){
if(result.containsKey(c)){
result.put(c,result.getOrDefault(c,0)-1);
}
}
for(int val : result.values()){
if(val > 0){
return false;
}
}
return true;
}
}
15. 3Sum
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
Set<List<Integer>> ans=new HashSet<>();
for(int i = 0; i < nums.length-2; i++){
int p1 = i+1;
int p2 = nums.length-1;
while(p1 < p2){
int sum = nums[i]+nums[p1]+nums[p2];
if(sum == 0){
ArrayList<Integer> sp = new ArrayList<>();
sp.add(nums[i]);
sp.add(nums[p1]);
sp.add(nums[p2]);
ans.add(sp);
p1++;
}
else if(sum < 0){
p1++;
}
else{
p2--;
}
}
}
return new ArrayList<>(ans);
}
}
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.length; i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
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]));
// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
}
18. 4Sum
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>>ans=new ArrayList<>();
if(nums==null || nums.length==0) return ans;
int n=nums.length;
Arrays.sort(nums);
for(int i=0;i<n;i++){
long target2=(long)target-(long)nums[i];
for(int j=i+1;j<n;j++){
long remaining=(long)target2-(long)nums[j];
int first=j+1;
int last=n-1;
while(first<last){
long twoSum=(long)nums[first]+(long)nums[last];
if(twoSum<remaining) {
first++;
}
else if(twoSum>remaining) {
last--;
}
else{
List<Integer>res=new ArrayList<>();
res.add(nums[i]);//num 1
res.add(nums[j]);//num 2
res.add(nums[first]);//num 3
res.add(nums[last]);//num 4
ans.add(res);
// Processing the duplicates of number 3
while(first<last && nums[first]==res.get(2)) first++;
// Processing the duplicates of number 4
while(first<last && nums[last]==res.get(3)) last--;
}
}
// Processing the duplicates of number 2
while(j+1<n && nums[j+1]==nums[j]) j++;
}
// Processing the duplicates of number 1
while(i+1<n && nums[i+1]==nums[i]) i++;
}
return ans;
}
}
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++) {
// nums[i] > target 直接返回, 剪枝操作
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) {
// nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
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;
}
}