* Sum of three numbers （ Medium questions ）
Given an inclusion n An array of integers nums, judge nums Are there three elements in a,b,c , bring a + b + c = 0
? Find all triples that satisfy the condition and do not repeat .
be careful ： The answer cannot contain duplicate triples .
Examples ：
Given array nums = [-1, 0, 1, 2, -1, -4],
The set of triples satisfying the requirements is ：
[
[-1, 0, 1],
[-1, -1, 2]
]
method code ： class Solution { public static List<List<Integer>> threeSum(int[] nums)
{ List<List<Integer>> result = new ArrayList<>(); int len = nums.length; if(nums
.length < 3) return result; Arrays.sort(nums); for(int i = 0 ; i < len; i++) {
if(nums[i] > 0 ) break; if(i>0 && nums[i] == nums[i-1]) continue; int l = i+1, r
= len -1; while(l < r) { int sum = nums[i] + nums[l] + nums[r]; if(sum == 0) {
result.add(Arrays.asList(nums[i],nums[l],nums[r])); while(l < r && nums[l] ==
nums[l+1]) l++; while(l < r && nums[r] == nums[r-1]) r--; l++; r--; } else if(
sum> 0) r--; else if(sum < 0) l++; } } return result; } }
Method analysis ：
label ： Array traversal
First, sort the array , Fixed number after sorting nums[i], Then use the left and right pointer to point to nums[i] The back ends , The numbers are nums[l]
and nums[r], Calculate the sum of three numbers sum Whether it is satisfied or not is determined as 0, If satisfied, it is added to the result set
If nums[i] greater than 0, The sum of the three must not be equal 0, End cycle
If nums[i] == nums[i−1], The number is repeated , It can lead to duplicate results , So you should skip
When sum== 0 Time ,nums[l] == nums[l+1] Will result in duplicate results , It should be skipped ,L++
When sum == 0 Time ,]nums[r] ==nums[r−1] Will result in duplicate results , It should be skipped ,R–
Time complexity ：O(n^2),n Is the array length

* The sum of the nearest three numbers （ Medium questions ）
Given an include n An array of integers nums and A target value target. find nums Three integers in , So that their sum and target
Closest . Returns the sum of these three numbers . Assume that there is only one answer for each input .
for example , Given array nums = [-1,2,1,-4], and target = 1.
And target The sum of the three nearest numbers is 2. (-1 + 2 + 1 = 2).
method code ： class Solution { public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums); int len = nums.length; int result = nums[0] + nums[1] +nums[2
]; if(len < 3) return target; if(len == 3) return result; int sum = Math.abs(
target- result); for(int i = 0 ;i < len - 2 ; i++) { int l = i + 1; int r = len
-1; while(l < r) { int ans = nums[i] + nums[l] + nums[r]; if(sum > Math.abs(
target- ans)) { sum = Math.abs(target - ans); result = ans; } if(sum == 0)
return target; if(ans > target) { while(l < r && nums[r] == nums[r-1]) r--; r--;
} else if(ans < target){ while(l < r && nums[l] == nums[l+1]) l++; l++; } } }
return result; } }
Method analysis ：
label ： Sort and double pointer
The problem is to calculate three numbers , If we use brute force to enumerate, the time complexity will arrive O(n^3), Need to reduce time complexity
First, sort the array , Time complexity O(nlogn)
In array nums in , Traverse , Each traversal of a value uses its subscript i, Form a fixed value nums[i]
Pointer before reuse l = i + 1 place , The back pointer points to r = nums.length - 1 place , That's the end
according to ans = nums[i] + nums[l] + nums[r] The results of , judge ans And goals target Distance of , Update results if closer result
Simultaneous judgment ans And target Size relation of , Because the array is ordered , If ans > target be r–, If sum < target be l++, If
ans == target Then the distance is 0 Return results directly , The whole traversal process , The fixed value is n second , The double pointer is n second , The time complexity is O(n^2)
Total time complexity ：O(nlogn) + O(n^2) = O(n^2)

* Sum of four numbers （ Medium questions ）
Given an inclusion n An array of integers nums And a target value target, judge nums Are there four elements in a,b,c and d , bring a + b + c
+ d The value of target equal ? Find all quaternions that satisfy the condition and do not repeat .
be careful ：
Examples ：
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
The set of quads satisfying the requirements is ：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
method code ： class Solution { public List<List<Integer>> fourSum(int[] nums, int
target) { List<List<Integer>> res = new ArrayList<>(); int len = nums.length; if
(len < 4 || nums == null) return res; Arrays.sort(nums); for(int i = 0 ; i < len
-3 ; i++) { if((nums[i] + nums[len-1] + nums[len-2] + nums[len-3]) < target)
continue; if((nums[i] + nums[i+1] + nums[i+2] + nums[i+3]) > target) continue;
for(int j = len - 1 ; j >= 3; j--) { if(i < j) { int r = j-1; int l = i+1; while
(l < r) { int sum = nums[i] + nums[j] + nums[r] + nums[l]; if(sum == target) {
nums[r]); s.add(nums[j]); res.add(s); while(l < r && nums[l] == nums[l + 1]) l++
; while(l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if(sum > target)
{ while(l < r && nums[r] == nums[r - 1]) r--; r--; } else if (sum < target) {
while(l < r && nums[l] == nums[l + 1]) l++; l++; } } } while(i < j && nums[j] ==
nums[j-1]) j--; } while(i < len-3 && nums[i] == nums[i+1]) i++; } return res; }
}
Method analysis ：

This problem is similar to the sum of the three numbers above , It's just that this problem uses three pointers , Fix the first one and the last one first , And then the other two bases sum To adjust , Then move the last pointer , Repeat the previous step , After the last encounter with the first , The first pointer moves back .

* Alphabetic combination of telephone numbers （ Medium questions ）
Given a number only 2-9 String of , Returns all combinations of letters it can represent .
Give the number to letter mapping as follows （ Same as phone key ）. be careful 1 Does not correspond to any letters .

Examples :
input ：“23”
output ：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
method code ： class Solution { String[] strs = {" ", "*" , "abc" , "def" , "ghi" ,
"jkl" , "mno" , "pqrs" , "tuv" , "wxyz"} ; List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) { if(digits == null ||
digits.length() == 0) return new ArrayList<>(); combination(digits, "", 0);
return res; } void combination(String digits ,String letter, int index ) { if(
index== digits.length()) { res.add(letter); return; } String s = strs[digits.
charAt(index)-'0']; for (int i = 0; i < s.length(); i++) { combination(digits ,
letter+ s.charAt(i) , index+1); } } }
Method analysis ：

This method is solved by recursion , Every time letter The letters corresponding to the new numbers are spliced in turn , Know all the numbers have been traversed , Take what you get in the end letter Add to list In the set .

* Delete the penultimate of the linked list N Nodes （ Medium questions ）
Given a linked list , Delete the penultimate of the linked list n Nodes , And return the head node of the linked list .
Examples ：
Given a linked list : 1->2->3->4->5, and n = 2.
When the penultimate node is deleted , The linked list becomes 1->2->3->5.
explain ：
Given n The guarantee is valid .
method code ： /** * Definition for singly-linked list. * public class ListNode { *
int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution {
ListNode second= head; for(int i = 0 ; i < n; i++){ if(first == null){ return
null; } else{ first = first.next; } } if(first == null) return head.next; while(
first.next !=null){ first = first.next; second = second.next; } second.next =
Method analysis ：

The method is through the pointer , Let the first pointer go first n step , Then let the first and second pointer go at the same time , When the next node of the first pointer is NULL Time , Then the next node of the second pointer is the penultimate n Nodes , Delete . This problem can also be solved by stack .

* Valid parentheses （ Medium questions ）
A given one contains only ‘(’,’)’,’{’,’}’,’[’,’]’ String of , Determine whether the string is valid .
Valid string must satisfy ：
The left bracket must be closed with the same type of right bracket .
The left bracket must be closed in the correct order .
Note that an empty string can be considered a valid string .
Examples 1:
input : “()”
output : true
Examples 2:
input : “([)]”
output : false
method code ： class Solution { public boolean isValid(String s) { int len = s.length()
; char[] c = s.toCharArray(); char[] stack = new char[len]; int top = -1; for(
int i = 0; i < len ;i++){ if(c[i] == ' ') continue; if(c[i] == '(' || c[i] ==
'{' || c[i] == '[') { stack[++top] = c[i]; continue; } if(c[i] == ')' && (top ==
-1 || stack[top--] != '(')) return false; if(c[i] == '}' && (top == -1 || stack[
top--] != '{')) return false; if(c[i] == ']' && (top == -1 || stack[top--] !=
'[')) return false; } if(top != -1) return false; else return true; } }

Method analysis ： This method is solved by using the idea of stack , When the left bracket is encountered , All pushed into the stack , When the right bracket is encountered , Stack top empty return false, Not empty stack top element , Check that the out of stack element matches the right bracket , Return if not matched false, Match and continue the loop , Finally, exit the loop , If top by -1, Return to true, Otherwise return false.

Technology
Daily Recommendation
views 5