This is the 17th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021
LeetCode1 Sum of two numbers solution
The title
Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice.
For example: given nums = [2, 7, 11, 15], target = 9 because nums[0] + nums[1] = 2 + 7 = 9
Their thinking
Idea one is a violent solution
It is easy to find the two values of the answer by nesting the two layers of the loop. The time complexity is O(n^2), but this method is time-consuming and will time out after submitting.
Idea two: Hash table
Because the time complexity of finding a value in a hash table is O(1), a hash table can be used to quickly find a value through key-value. For each element nums[I], look for target-nums[I] in the HashMap. If you find it, you will find the answer. Otherwise, there is no solution.
The code shown
Idea one is a violent solution
public int[] twoSum(int[] nums, int target) {
int a[] = new int[2];
a[0] = a[1] = 0;
for(int i=0; i< nums.length; i++) {for(int j=i+1; j< nums.length; j++) {if(nums[i]+nums[j]==target)
{
a[0] = i;
a[1] = j;
returna; }}}return a;
}
Copy the codeIdea two: Hash table
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0; i< nums.length; i++) { map.put(nums[i],i); }for(int i=0; i< nums.length; i++) {int comp = target - nums[i];
if(map.containsKey(comp)&&map.get(comp)! =i) {int a[] = new int[2];
a[0] = i;
a[1] = map.get(comp);
returna; }}return new int[2];
}
Copy the codeLeetCode15 Solution to the sum of three numbers
The title
Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that meet the criteria and are not duplicated.
Note: Repeated triples cannot be included in the answer.
For example, given the array nums = [-1, 0, 1, 2, -1, -4],
The set of triples that meet the requirements is: [[-1, 0, 1], [-1, -1, 2]]
Their thinking
Idea one is a violent solution
It’s pretty easy to figure out that you can solve it violently with three levels of loop nesting, but the time is O(n^3), so I didn’t try.
Idea 2 Single-layer loop + dual pointer
To prevent the output from containing duplicate triples, sort the original array first. You can use the built-in quick sort function with the time complexity of O(nlogn). For each array value nums[I], only two array values nums[a] and nums[b] (b>a> I) need to be found after subscript I, such that nums[a]+nums[b]==0-nums[I]. Enter the current array values nums[I], I +1 (left pointer), nums.length-1 (right pointer), and the array nums into the function Twosum () to find the desired nums[a] and nums[b].
When nums[left]+num[right]>-nums[I], move the right pointer to the left. Nums [left]+num[right]<-nums[I] Nums [left] ==nums[left]; nums[left] ==nums[left]; nums[left] ==nums[left]; We need to move the left pointer right to exclude duplicate values, and do the same for the right pointer. Finally, the left and right Pointers will move the middle one time for the next search.
For example
For the array [-1,0,1,2,-1,4], we need three digits to sum them to 0, sorting them first.
When I =0, nums[I]=-4, there are no two remaining numbers in this array that sum to 4.
If nums[I]=-1 and nums[I]=-1 and nums[I]=-1 and nums[I]=-1 and nums[I]=-1 and nums[I]=-1 and nums[I]=-1
The left pointer points to 0, and the right pointer points to 1. The condition is met: 0+1 = 0- (-1)
Because nums[1]==nums[2] is found when I =2, so we skip I =2 and enter I =3, there is no qualified value.
The code shown
public static List<List<Integer>> Twosum(int start,int end,int nums[],int value)
{
List<List<Integer>> list = new ArrayList<>();
while(start<end)
{
if(start<end)
{
int a = nums[start];
int b = nums[end];
while(nums[start]+nums[end]>(0-value)&&start<end)
{
end--;
}
while(nums[start]+nums[end]<(0-value)&&start<end)
{
start++;
}
if(nums[start]+nums[end]==(0-value)&&start<end)
{
List<Integer> alist = new ArrayList<>();
alist.add(value);
alist.add(nums[start]);
alist.add(nums[end]);
list.add(alist);
// Prevent duplication
while(start! = nums.length-1&&nums[start+1]==nums[start])
start++;
while(end! =0&&nums[end]==nums[end-1])
end--;
if(start>=end)
break; start++; end--; }}}return list;
}
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i< nums.length; i++) {if(i>0&&nums[i]==nums[i-1])
continue;
List<List<Integer>> alist = Twosum(i+1, nums.length-1,nums,nums[i]);
for (int j=0; j<alist.size(); j++) list.add(alist.get(j)); }return list;
}
Copy the codeLeetCode18 Solution to the sum of four numbers (with pseudo code steps)
The title
Given an array nums containing n integers and a target value target, determine whether there are four elements a, B, c, and D in nums such that a + b + C + D is equal to target. Find all quaternions that meet the condition and are not duplicated.
For example: given the array nums = [1, 0, -1, 0, -2, 2], and target = 0. Meet the requirements of the quad sets for: [[- 1, 0, 0, 1], [2, 1, 1, 2], [2, 0, 0, 2]]
Their thinking
LeetCode # 1 “Sum of two numbers” and LeetCode # 15 “Sum of three numbers” have been written before
The original array is sorted first, preventing duplicate quads from appearing in the result. After iterating through the nums array, add the I +1 element to the last element to form a new array. Search for three numbers in the new array so that their sum is equal to target-nums [I]. The next step is to call the function of the sum of three numbers to find. If nums[I]==nums[i-1], skip this traversal to prevent duplicate quads.
Pseudocode step
- Step1: Sort the NUMS array
- Step2: iterate through the nums array
- Step3: if the current array value is equal to the previous array value, then skip this loop
- Step4: form a new array of values following the current array values
- Step5: call the threesum() function to retrieve any triples that meet the criteria
- Step6: Form the triples found and the current values into quads respectively
The code shown
public static List<List<Integer>> Twosum(int start,int end,int nums[],int value,int target)
{
List<List<Integer>> list = new ArrayList<>();
while(start<end)
{
if(start<end)
{
int a = nums[start];
int b = nums[end];
while(nums[start]+nums[end]>(target)&&start<end)
{
end--;
}
while(nums[start]+nums[end]<(target)&&start<end)
{
start++;
}
if(nums[start]+nums[end]==(target)&&start<end)
{
List<Integer> alist = new ArrayList<>();
alist.add(value);
alist.add(nums[start]);
alist.add(nums[end]);
list.add(alist);
// Prevent duplication
while(start! = nums.length-1&&nums[start+1]==nums[start])
start++;
while(end! =0&&nums[end]==nums[end-1])
end--;
if(start>=end)
break; start++; end--; }}}return list;
}
public static List<List<Integer>> threeSum(int[] nums,int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
for(int i=0; i< nums.length; i++) {if(i>0&&nums[i]==nums[i-1])
continue;
List<List<Integer>> alist = Twosum(i+1, nums.length-1,nums,nums[i],target - nums[i]);
for (int j=0; j<alist.size(); j++) list.add(alist.get(j)); }return list;
}
public static List<List<Integer>> fourSum(int[] nums,int target)
{
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i=0; i< nums.length-2; i++) {if(i>0&&nums[i]==nums[i-1])
continue;
int a[] = new int[nums.length-i-1];
for (int j = 0; j<a.length; j++) { a[j] = nums[i+j+1];
}
List<List<Integer>> alist = threeSum(a,target-nums[i]);
for (int j=0; j<alist.size(); j++) { List<Integer> list =new ArrayList<>();
list.add(nums[i]);
for (int t=0; t<alist.get(j).size(); t++) { list.add(alist.get(j).get(t)); } res.add(list); }}return res;
}
Copy the code