Field 1	Field 1 link	difficulty	Recent inspection time	Frequency test	notes
1. Sum of two numbers	https://leetcode-cn.com/problems/two-sum	easily	2021/4/24	8	The sum of the two numbers of this topic 1 is topic 15 The deformation of the sum of three. The initial idea is: first sort the array, and then use the double pointer method to approximate the result. However, sorting will change the index of the array, and the result to be returned is the index of the array. This is not possible. hashmap is required. Using hashmap storage, key is nums[i], val is I.
Longest non repeating character string	https://leetcode-cn.com/problems/longest-substring-without-repeating-characters	secondary	2021/4/14	8	When you encounter the substring problem, the first thing you think of is the sliding window technique. Sliding window means moving the right pointer to add data to the window and moving the left pointer to delete data. In addition, note that when hashmap val=0, it will occupy space. You need to manually remove (when hashmap.size() is used as the return result), otherwise, use right left.
20. Valid brackets	https://leetcode-cn.com/problems/valid-parentheses	easily	2021/4/22	6	Through example 5 "{[]}", we can know that this topic needs the help of the nature of the stack: first in and then out. My writing is very complicated and not concise. Often brush familiar routines. The details are s.toCharArray(), stacksack = new stack < > ();! stack. isEmpty(). Finally, judge whether the stack is empty. If not, for example, there is still '{[(', indicating that there is still room left, then return false;
704. Binary search	https://leetcode-cn.com/problems/binary-search	easily	2021/4/20	6	In the back-end, the test frequency accounts for a small proportion. This topic is the classic template topic of binary search.
141. Circular linked list	https://leetcode-cn.com/problems/linked-list-cycle	easily	2021/4/27	5	Just have to recite the memory and brush it repeatedly. The classic solution is to use two pointers, one running fast and the other running slow. If it does not contain rings, the pointer running fast will eventually encounter null, indicating that the linked list does not contain rings; If it contains a ring, the fast pointer will eventually make a turn of the super slow pointer and meet the slow pointer, indicating that the linked list contains a ring.

1. Sum of two numbers

The basic form of this problem is as follows: give you an array and an integer target, which can ensure that the sum of two numbers in the array is target. Please return the index of these two numbers.

For the TwoSum problem, one difficulty is that the given array is out of order. For an unordered array, we don't seem to have any skills. We can only violently enumerate all the possibilities.

Generally, we will sort the array first, and then consider the double pointer technique. TwoSum inspired us that HashMap or HashSet can also help us deal with simple problems related to unordered arrays.

The sum of the two numbers of this topic 1 is topic 15 The deformation of the sum of three. The initial idea is: first sort the array, and then use the double pointer method to approximate the result. However, sorting will change the index of the array, and the result to be returned is the index of the array. This is not possible. hashmap is required. Using hashmap storage, key is nums[i], val is I.

code:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Using hashmap storage, key is nums[i], val is I
        HashMap<Integer,Integer>map=new HashMap<>();
        // Traverse array elements
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{i,map.get(target-nums[i])}; 
            }
            // In hashmap, key is nums[i], val is I
            map.put(nums[i],i);
        }
        // Indicates that the result does not exist
        return new int[]{};
    }
}

Double pointer doesn't work

The initial idea is: first sort the array, and then use the double pointer method to approximate the result. However, sorting will change the index of the array, and the result to be returned is the index of the array. This is not possible.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Firstly, the array is sorted, and then the double pointer method is used to approximate the result
        Arrays.sort(nums);
        int left=0,right=nums.length-1;
        while(left<right){
            int sum=nums[left]+nums[right];
            if(sum<target){
                left++;
            }else if(sum>target){
                right--;
            }else{
                return new int[]{left,right};
            }
        }
        return new int[]{};
    }
}

3. Longest substring without duplicate characters

When you encounter the substring problem, the first thing you think of is the sliding window technique. Sliding window means moving the right pointer to add data to the window and moving the left pointer to delete data. In addition, note that when hashmap val=0, it will occupy space. You need to manually remove (when hashmap.size() is used as the return result), otherwise, use right left.

Remember: pseudo code framework:

string s, t;
// Find the "minimum covering substring" of t in s
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
    window.add(s[right]);
    right++;
    // If it meets the requirements, move left to narrow the window
    while (window Meet the requirements) {
        // If the substring of this window is shorter, update res
        res = minLen(res, window);
        window.remove(s[left]);
        left++;
    }
}
return res;

Similar to the previous idea, use window as a counter to record the number of characters in the window, and then move right first. When repeated characters appear in the window, start moving left to narrow the window, and so on:

class Solution {
    // The problem here is to find the substring. The substring cannot be separated.
    public int lengthOfLongestSubstring(String s) {
        // Define a returned result
        int maxLen=0;
        // Use hashMap to avoid duplicate characters in the results
        HashMap<Character,Integer>window=new HashMap<>();
        // Use double pointer
        int left=0,right=0;
        // Traversal in a large loop
        while(right<s.length()){
            // Value
            char c1=s.charAt(right);
            right++;
            // Save to window
            window.put(c1,window.getOrDefault(c1,0)+1);
            // If the character is repeated at this time, move the pointer
            while(window.get(c1)>1){
                // Remove the value of left
                char c2=s.charAt(left);
                left++;
                window.put(c2,window.getOrDefault(c2,0)-1);
                // It should be noted here that when value=0, the key is not cleared.
                if(window.get(c2).equals(0)){
                    window.remove(c2);
                }
            }
            // Update the length at this time
            maxLen=Math.max(maxLen,window.size());
        }
        return maxLen;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;
        HashMap<Character, Integer> window = new HashMap<>();
        int resMaxLen = 0;
        while (right < s.length()) {
            char c1 = s.charAt(right);
            window.put(c1, window.getOrDefault(c1, 0) + 1);
            right++;
            // If duplicate characters appear in the window
            // Start moving left to narrow the window
            while (window.get(c1) > 1) {
                char c2 = s.charAt(left);
                window.put(c2, window.getOrDefault(c2, 0) - 1);
                left++;
            }
            resMaxLen = Math.max(resMaxLen, right - left);
        }
        return resMaxLen;
    }
}

It should be noted that because we require the longest substring, we need to update res every time we move right to increase the window, rather than update res when we move left to narrow the window as in the previous topic.

20. Valid brackets

Through example 5 "{[]}", we can know that this topic needs the help of the nature of the stack: first in and then out. My writing is very complicated and not concise. Often brush familiar routines. The details are s.toCharArray(), stacksack = new stack < > ();! stack. isEmpty(). Finally, judge whether the stack is empty. If not, for example, there is' {[(', indicating that there is still room left, then return false;

20. Valid brackets

//Basic idea: each time an open bracket is encountered, the corresponding right bracket ')', ']' or '}' will be pushed onto the stack
//If a closing bracket appears in the string, you need to check whether the stack is empty and whether the top element is the same as the closing bracket. If not, the string is invalid.
//Finally, we also need to check whether the stack is empty
class Solution {
    public boolean isValid(String s) {
        // Using the nature of stack, first in, first out
        Stack<Character>stack=new Stack<>();
        // Traversing the elements of a string
        for(char sc:s.toCharArray()){
            if(sc=='{'){
                stack.push('}');
            }else if(sc=='['){
                stack.push(']');
            }else if(sc=='('){
                stack.push(')');
            }else if(!stack.isEmpty()&&sc==stack.peek()){
                stack.pop();
            }else{
                return false;
            }
        }
        // Finally, judge whether the stack is empty. If not, for example, there is still '{[(', indicating that there is still room left, then return false;
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }
}

704. Binary search

https://leetcode-cn.com/problems/binary-search

In the back-end, the test frequency accounts for a small proportion. This topic is the classic template topic of binary search.

704. Binary search

class Solution {
    public int search(int[] nums, int target) {
        // The array is in ascending order, so there is no need to sort manually. Because the subscript needs to be returned, the title can only be sorted.
        // Using binary search, this topic is the classic template topic of binary search
        //Left and right boundary
        int left=0,right=nums.length-1;
        while(left<=right){
            //Index of midpoint
            int mid=(right-left)/2+left;
            if(nums[mid]<target){
                // Change the interval to [mid+1,right]
                left=mid+1;
            }else if(nums[mid]>target){
                // Change the interval to [left,mid-1]
                right=mid-1;                
            }else if(nums[mid]==target){
                // If the result is found, the result subscript is returned
                return mid;
            }
        }
        // non-existent
        return -1;
    }
}

Binary search framework

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

141. Circular linked list

https://leetcode-cn.com/problems/linked-list-cycle

Just have to recite the memory and brush it repeatedly. The classic solution is to use two pointers, one running fast and the other running slow. If it does not contain rings, the pointer running fast will eventually encounter null, indicating that the linked list does not contain rings; If it contains a ring, the fast pointer will eventually make a turn of the super slow pointer and meet the slow pointer, indicating that the linked list contains a ring.

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            //The two met
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}