Leetcode topic

Catalog

Sum of two numbers

  Longest substring without repeating characters

Longest text substring

Sum of three numbers

Add one

There are duplicate elements

Move 0

Intersection of two arrays

---

Sum of two numbers

Given an array of integers nums  And an integer target value target, Please find... In the array And is the target value target   the   Two   Integers , And return their array subscripts .

Input ：nums = [2,7,11,15], target = 9
Output ：[0,1]
explain ： because nums[0] + nums[1] == 9 , return [0, 1] .

1. Create a map,for Loop traversal nums Array
2. use target reduce nums[i]（ Calculate which number is added to the current number to get target）
3. Check map Is there such a number in the （ If yes, the result is returned , If you don't put nums[i] treat as key,i treat as value Put in map in ）
4. map.has（） Check map Is there any current key

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
const map =new Map();
for(let i=0;i<nums.length;i++){
    const num=target-nums[i]
    if(map.has(num)){
        return[map.get(num),i]
    }else{
        map.set(nums[i],i)
    }
}
    return []
};

  Longest substring without repeating characters

Given a string  s , Please find out that there are no duplicate characters in it   Longest substrings   The length of .

 Input : s = "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its  The length is  3.

• Create a set
• Two pointers , The first pointer points to the beginning of the string （j）. The second one follows for Loop through the string （i）
• If set Not in it s[i], It indicates that there is no duplicate string so far s[i] Add to set Inside , Update the maximum number of non repeating characters
• If set There are s[i] From set Delete s[j], And increasing , Checking set Is there s[i]
• So repeatedly until set There's no s[i] until , Until the entire array is traversed

Sliding window algorithm

What is a sliding window ？

It's actually a queue , For example, in the example abcabcbb, Enter this line （ window ） by abc Meet the requirements of the topic , When you enter a, The queue becomes abca, Not meeting the requirements at this time . therefore , We're going to move this queue ！

How to move ？

All we have to do is move the elements on the left side of the queue , Until the subject requirements are met ！

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const set=new Set()
    let i=0,j=0,maxlen=0;
    if(s.length=0){
        return 0
    }
    for(i;i<s.length;i++){
        if(!set.has(s[i])){
            set.add(s[i])
            maxlen=Math.max(maxlen,set.size)
        }else{
            while(set.has(s[i])){
                set.delete(s[j])
                j++
            }
            set.add(s[i])
        }
    }
    return maxlen
};

Longest text substring

You need a string  s, find  s  The longest palindrome substring in .

 Input ：s = "babad"
 Output ："bab"
 explain ："aba"  It's the same answer .

1. If the string length is less than 2, Return the original string directly
2. Define two variables start Store the starting position of the largest palindrome string currently found , the other one maxlen Record the length of the string （ The end position is start+mexlen）mexlen=1(ab)
3. Create a helper function Judge whether the left and right cross the boundary , At the same time, the leftmost character is equal to the rightmost character , If all three conditions are met , Then judge whether to update the maximum length of palindrome string , then left--,right++, Continue to judge , Until one of the three conditions is not met
4. Traversal string , Each location calls helper function Two times First pass i-1,i+1(babad There is a central point ) Second times i,i+1(cabbad There is no central point )

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    //  The string is less than 2, Returns the string 
if(s.length<2){
    return s
}
//  The starting position , And maximum length   The default maximum length should be 1（ab  The biggest palindrome should be 1）
let start=0,maxlen=1;
function expandAroundCenter(left,right){
    // Judge whether the left and right cross the boundary , At the same time, the left character is equal to the right character 
    while(left>=0&&right<s.length&&s[left]===s[right]){
        // Determine whether to update the maximum length of palindrome string 
        if(right-left+1>maxlen){
            maxlen=right-left+1
            start=left
        }
        left--;
        right++;
    }
}
for(let i=0;i<s.length;i++){
    expandAroundCenter(i-1,i+1)
    expandAroundCenter(i,i+1)
}
return s.substring(start,start+maxlen)
};

Sum of three numbers

Give you one containing n Array of integers  nums, Judge  nums  Are there three elements in a,b,c , bring  a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

 Input ：nums = [-1,0,1,2,-1,-4]
 Output ：[[-1,-1,2],[-1,0,1]]

1. Sort array
2. Traversal array , from 0 Traversing length-2（ To prevent cross-border ）
3. If the current number , If it is equal to the previous number, skip this number （ Avoid duplicates ）
4. If the numbers are different , Is set start=i+1,end=length-1, see i start end The sum ratio of three numbers 0 Big or small , If you compare 0 Small start++, Than 0 Big end--, If it is equal to 0 Add three numbers to the result
5. Return results

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
let result=[]
nums.sort(function(a,b){
    return a-b
})
// To prevent cross-border 
for(let i=0;i<nums.length-2;i++){
    // If it's the first element , Or if two numbers are equal, there is no need to compare 
    if(i===0||nums[i]!==nums[i-1]){
    let start=i+1,
        end=nums.length-1;
        // After the two numbers meet, the cycle ends 
        while(start<end){
            // If equal, return an array 
            if(nums[i]+nums[start]+nums[end]===0){
                // Remember to remove the weight when moving 
                result.push([nums[i], nums[start], nums[end]])
                start++
                end--
                // start If you want to continue to indent backward with the previous ratio 
                while(start<end&&nums[start]===nums[start-1]){
                    start++
                }
                // end  Compare with the latter , If equal, continue to indent forward 
                 while(start<end&&nums[start]===nums[end+1]){
                    end--
                }
            // Less than 0 start++
            }else if(nums[i]+nums[start]+nums[end]<0){
                start++
            }else{//  Greater than 0end--
                end--
            }
        }
    }
}
return result
};

Add one

Given a by Integers Composed of Non empty The nonnegative integer represented by an array , Add one to the number .

The highest digit is placed at the top of the array , Each element in the array stores only a single number .

You can assume that except for integers 0 outside , This integer will not start with zero .

 Input ：digits = [1,2,3]
 Output ：[1,2,4]
 explain ： Input array represents number  123.

 1. Inverted circular array
2. If the current item is not equal to 9 Direct addition 1 Bit return array  
3. If it is 9 Change the current item to 0 Continue to cycle
4. If all equal 0 Spell it 1

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
for(let i=digits.length-1;i>=0;i--){
    if(digits[i]!==9){
        digits[i]++
        return digits
    }else{
        digits[i]=0
    }
}
const result=[1,...digits]
return result
};

There are duplicate elements

Give you an array of integers  nums . If any value appears in the array   At least twice  , return  true ; If each element in the array is different from each other , return  false .

 Input ：nums = [1,2,3,1]
 Output ：true

  establish set structure

Loop array judgment set There is no such value in There is a return true

No, add Additional The end of the loop does not return Then for false

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
let set =new Set()
for(let i=0;i<nums.length;i++){
    if(set.has(nums[i])){
        return true
    }else{
        set.add(nums[i])
    }
}
return false
};

Move 0

Given an array  nums, Write a function that will  0  Move to end of array , While maintaining the relative order of non-zero elements .

Please note that  , You must operate on the array in place without copying it .

 Input : nums = [0,1,0,3,12]
 Output : [1,3,12,0,0]

 

Declare a pointer j
Circular array i If not, move to j The location of j++
The loop ends Fill the remaining positions 0

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
 let j = 0;

        for (let i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
            }
        }

        for (i = j; i < nums.length; i++) {
            nums[i] = 0
        }

        return nums
};

Intersection of two arrays

Given two arrays  nums1  and  nums2 , return   Their intersection  . Every element in the output must be   only   Of . We can   Regardless of the order of the output results  .

 Input ：nums1 = [1,2,2,1], nums2 = [2,2]
 Output ：[2]

establish set structure Because there are no duplicates
Circular array 1 includes Detect arrays 2 Include in 1 The content of contain add Additional
array.from Converted to an array  

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
let set =new Set()
for(let i=0;i<nums1.length;i++){
   if( nums2.includes(nums1[i])){
      set.add(nums1[i])
    }
}
 return Array.from(set)
};