LeetCode Day6 HashTable Part2
Flame Chan
Posted on June 12, 2024
LeetCode No.454 4Sum 2
Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Example 1:
Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
- (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0 Example 2:
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1
A direct way to solve the problem but it will cause Time Limit Exceeded Because it is O(n^4) lol... crazy！
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int count = 0;
for(int i:nums1){
for(int j:nums2){
for(int k: nums3){
for(int l: nums4){
if(i+j+k+l == 0){
count++;
}
}
}
}
}
return count;
}
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int count = 0;
Map<Integer,Integer> map = new HashMap<>();
for(int i:nums1){
for(int j:nums2){
// record the number of corrolation [1,1] [2,0] are the same
map.put(i+j,map.getOrDefault(i+j, 0) + 1);
}
}
for(int i:nums3){
for(int j : nums4){
int target = 0 - i -j;
count += map.getOrDefault(target, 0);
}
}
return count;
}
time: O(n^2), space: O(n)
getOrDefault is a very useful function
I think I should pay some attention to Java's collection's function.
LeetCode 383 Ransom Note
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
Example 1:
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:
Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:
Input: ransomNote = "aa", magazine = "aab"
Output: true
Orinigal Page
public boolean canConstruct(String ransomNote, String magazine) {
char[] ransomArr = ransomNote.toCharArray();
char[] mgzArr = magazine.toCharArray();
if(ransomArr.length > mgzArr.length){
return false;
}
boolean notFound = false;
for(int i=0; i<ransomArr.length; i++){
int j=i;
notFound = true;
for(int k=i; k<mgzArr.length; k++){
if(ransomArr[i] == mgzArr[k]){
char temp = mgzArr[k];
mgzArr[k] = mgzArr[j];
mgzArr[j] = temp;
notFound = false;
break;
}
}
if(notFound){
return false;
}
}
return true;
}
The time complexity is O(n·m), space complexity is O(n+m)
LeetCode No.15 3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Original Page
Use a direct thought to write it first. But this is the wrong code
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i < nums.length - 2; i++) {
for(int j = i + 1; j < nums.length - 1; j++) {
for(int k = j + 1; k < nums.length; k++) {
if(nums[i] + nums[j] + nums[k] == 0) {
list.add(Arrays.asList(nums[i], nums[j], nums[k]));
}
}
}
}
return list;
}
But this will cause some trouble containing duplicated result tuples e.g. [0,-1,1] and [-1,0,1] will be the same tuple in this question so we have to optimize the above code to achieve AC.
Using a double vector method may help because it is really difficult to conduct the problem that the array is not in-order as well as the we need to remove duplication
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
if(nums[0] > 0){
return new ArrayList<>();
}
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i < nums.length - 2; i++) {
if(nums[i] > 0){
return list;
}
// nums[i] == nums[i-1] and nums[i] == nums[i+1] will lead to different result !!!!!
if(i-1>=0 && nums[i] == nums[i-1]){
continue;
}
int left = i+1;
int right = nums.length-1;
// left < right means left must less than nums.length-1 because max right is nums.length-1 and right will decrease
while(left<right ){
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0){
while(left<right && nums[right-1]==nums[right]){
right--;
}
right--;
}else if(sum<0){
while(left<right && nums[left+1] == nums[left]){
left++;
}
left++;
}else{
list.add(Arrays.asList(nums[i], nums[left], nums[right]));
while(left<right && nums[right-1]==nums[right]){
right--;
}
while(left<right && nums[left+1] == nums[left]){
left++;
}
right --;
left ++;
}
}
}
return list;
}
the first version is not fine enough so I want to improve it
here we see that the inner while loop is for remove duplication for example [-1,-1,-1,-1,0,1,2,2,2,2]
if i=0 we have -1 so now left and right are -1 and 2 separately and the index of left and right is 1 and length-1 separately and our first result is [-1,-1,2].
but if we move the left to the right and move the right to the left
(index 0f left and right now is 2 and length-2) the result is the same result [-1,-1,2], and we do not want to see it. we want to cut these same elements down so we find left and right until get the different numbers.
This is the basic logic.
But we should be careful
- the sum of them <0 means left is too small we only shift left to the right
- the sum of them > 0 means the right is too large so we only move right to the left
- =0 means we find the result and we should save the result now.
(We have removed the
iduplicated element by using another inner loop)
so here the 2 inner loops is redundant because whatever happens, the out loop will continue because the inner loop's work can be replaced by out loop
Arrays.sort(nums);
if(nums[0] > 0){
return new ArrayList<>();
}
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i < nums.length - 2; i++) {
if(nums[i] > 0){
return list;
}
// nums[i] == nums[i-1] and nums[i] == nums[i+1] will lead to different result !!!!!
if(i-1>=0 && nums[i] == nums[i-1]){
continue;
}
int left = i+1;
int right = nums.length-1;
// left < right means left must less than nums.length-1 because max right is nums.length-1 and right will decrease
while(left<right ){
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0){
right--;
}else if(sum<0){
left++;
}
else{
list.add(Arrays.asList(nums[i], nums[left], nums[right]));
while(left<right && nums[right-1]==nums[right]){
right--;
}
while(left<right && nums[left+1] == nums[left]){
left++;
}
right--;
left++;
}
}
}
return list;
}
time: O(n^+nlogn)[sort: nlogn, other n^2], space: O(1) no extra space
Posted on June 12, 2024
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
