1. Sum of two numbers
Their thinking
- Think of NUMs as finding partners and the sum of the two partners is the target value
- You can use map to store peer data
/ * * *@param {number[]} nums
* @param {number} target
* @return {number[]}* /
var twoSum = function(nums, target) {
const m = new Map(a);for(let i = 0; i <= nums.length -1; i++) {
const c = nums[i];
// Calculate the target value
const find = target - c;
if(m.has(find)) {
// find the return subscript of the target value and the current value subscript
return [m.get(find),i];
} else {
// Put yourself into map for other values to look up
m.set(c, i)
}
}
};
Copy the code
3. The oldest string without repeating characters
Their thinking
- Start by finding all substrings that do not contain repeating characters
- Find the longest substring and return its length
- Maintains a sliding window with double Pointers for clipping substrings
- Keep moving the right pointer, and when it encounters a repeating character, move the left pointer to the next digit of the repeating character
- Process, record the length of all Windows and return the maximum value
/ * * *@param {string} s
* @return {number}* /
var lengthOfLongestSubstring = function(s) {
/ / pointer l
let l = 0;
let maxLength = 0;
// Stores no character values and subscripts
let map = new Map(a)for(let r = 0; r < s.length; r++) {const val = s[r];
// Repeat the value and move it to the next bit after the pointer
if(map.has(val) && map.get(val) >= l) {
l = map.get(val) + 1;
}
maxLength = Math.max(maxLength, r - l + 1)
map.set(val,r)
}
return maxLength;
};
Copy the code
76. Minimum coverage substring
Their thinking
- So let’s find all the substrings that contain T
- Find the smallest substring and return it
- Maintain a sliding window with double Pointers
- Move the right pointer to find the substring containing T, and move the left pointer to minimize the length of the substring containing T
- Loop the above process to find the smallest string containing T
/ * * *@param {string} s
* @param {string} t
* @return {string}* /
var minWindow = function(s, t) {
/ / pointer to the left
let l = 0;
/ / right pointer
let r = 0;
// The data dictionary value and the number of objects to look up
let need = new Map(a);for(let i of t) {
need.set(i, need.has(i) ? need.get(i) + 1 : 1);
}
// Number of characters
let needType = need.size;
// Minimum result
let res = ' ';
while(r < s.length) {
// loop over the right pointer
const c = s[r];
if(need.has(c)) {reduce the number of requirements need.set(c, need.get(c) -1);
if(need.get(c) === 0) {
needType -= 1; }}// Find the desired substring
while(needType === 0) {// Intercepts the character found
const newRes = s.substring(l,r+1)
// Compare the updated res to update the minimum length
if(! res || newRes.length < res.length) { res = newRes; }const c2 = s[l];
// Finding the character needed to update need will exit the loop and enter the upper loop
if(need.has(c2)) {
need.set(c2,need.get(c2) + 1);
if(need.get(c2) === 1) {
needType += 1;
}
}
l++
}
r++
}
return res;
};
Copy the code
2. Add two numbers
Their thinking
- Analog additive operation
- You need to walk through the list
- Arranged in reverse chronological order
- Create a new linked list
- Iterate over the two lists to be added, simulating the addition operation, appending the units digit to the new list and reserving the tens digit for the next digit to add
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}* /
var addTwoNumbers = function(l1, l2) {
const l3 = new ListNode(0);
// Declare three Pointers
let p1 = l1;
let p2 = l2;
let p3 = l3;
let i = 0;
while(p1 || p2) {
const v1 = p1 ? p1.val : 0;
const v2 = p2 ? p2.val : 0;
const val = v1 + v2 + i;
// Get the carry
i = Math.floor(val / 10);
/ / to take over
p3.next = new ListNode(Math.floor(val % 10));
if(p1) p1 = p1.next;
if(p2) p2 = p2.next;
p3 = p3.next;
}
if(i) {
p3.next = new ListNode(i);
}
return l3.next;
};
Copy the code