初级题目

Ⅰ栈

简单

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

解题思路

简单来讲就是先将字符串中的左括号{、(、[用一个栈存起来；然后遍历字符串，如果遇到右括号}、)、]就将栈中对应的括号弹出，遍历完字符串之后，如果栈为空，说明满足条件：

那么，这个容器为什么是栈？

• 我们继续往右扫，当遇到右括号，我们期待它匹配「最近出现的左括号」。
• 容器中的「最近出现的左括号」被匹配了，就不用等待匹配了，可以离开容器。
• 它是「后进」的，现在「先出」了，「后进先出」，所以是栈。
• 有点像消消乐。匹配了就拿掉，直到所有左括号都匹配光，则有效。如果还剩下左括号未匹配，则不有效。栈适合玩这个消消乐。

写法一

const isValid = (s) => {
  const stack = [];

  for (const cur of s) {
    if (cur == '{' || cur == '(' || cur == '[') { 
      stack.push(cur);   
    } else {                                     
      if (stack.length == 0) {                    
        return false;                            
      }
      const stackTop = stack[stack.length - 1];   
      if (
        stackTop == '(' && cur == ')' ||
        stackTop == '[' && cur == ']' ||
        stackTop == '{' && cur == '}'
      ) {                                        
        stack.pop();                       
      } else {   	              
        return false; 
      }
    }
  }
  // 考察完所有字符，如果此时栈空，说明左括号匹配光了，是有效字符串。
  // 如果栈中还剩有左括号没被匹配，则不是有效字符串。
  return stack.length == 0;
};

写法二

const isValid = (s) => {
  const map = { '{': '}', '[': ']', '(': ')' };
  const stack = [];

  for (const cur of s) {
    if (map[cur]) {                  
      stack.push(cur);             
    } else {                           
      if (stack.length == 0) {           
        return false;                 
      }
      const stackTop = stack[stack.length - 1]; 
      if (map[stackTop] == cur) {          
        stack.pop();                      
      } else {                           
        return false;                    
      }
    }
  }
  // 栈中是否还有未匹配的左括号
  return stack.length == 0; 
};

TIPS：能用const就不用let，能用let就不用var

**注意：**使用stackTop进行比较，也就是栈顶；

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

示例

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

方法一：创建两个栈

var MinStack = function() {
    this.x_stack = [];
    this.min_stack = [Infinity];
};

MinStack.prototype.push = function(x) {
    this.x_stack.push(x);
    this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));
};

MinStack.prototype.pop = function() {
    this.x_stack.pop();
    this.min_stack.pop();
};

MinStack.prototype.top = function() {
    return this.x_stack[this.x_stack.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.min_stack[this.min_stack.length - 1];
};

方法二：简单粗暴

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = []

};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    return this.stack.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return  this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return Math.min(...this.stack)
};

225. 用队列实现栈

JavaScript中没有队列结构，所以实现和上面的代码一致：

/**
 * Initialize your data structure here.
 */
var MyStack = function() {
  this.stack = []
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    this.stack.push(x)
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
   return this.stack.pop()
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return !this.stack.length
};

232. 用栈实现队列

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

示例

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

使用Array.shift()模拟队列的出队操作，配合Array.push()实现队列的先进先出特性：

/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.queue = []
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.queue.push(x)
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    return this.queue.shift()
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    return this.queue[0]
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return !this.queue.length
};

496. 下一个更大元素 I

给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

方法一：糟糕的解题方式

思路：

• 遍历nums1，找出当前元素val在nums2中的位置；
• 再nums2中截取该位置到末尾的子数组；
• 遍历子数组，将比val大的元素通过临时变量temp存起来
• 根据temp是否为空，进行下一步操作；

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    const res = []
    for(let val of nums1){
        let index = nums2.indexOf(val)
        let arr = nums2.slice(index + 1)
        let temp = []
        arr.forEach(e => {
            if(e > val){
                temp.push(e)
            }
        })
        if(temp.length){
            res.push(temp[0])
        }else{
            res.push(-1)
        }
    }
    return res
};

方法二：

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    return nums1.map(num1=>nums2.slice(nums2.indexOf(num1)+1).find(num2=>num2>num1)||-1)
};

方法三

维护一个单调递减栈

var nextGreaterElement = function(nums1, nums2) {
 //整体思路：
 //1.维护一个单调递减的栈，如果遇到比栈顶大的元素就是第一个比自己大的了
 //2.那么用key表示当前的数，nums[i]表示比key大的第一个数
 //3.枚举nums1找存在的key里的value值即可
  let map = new Map()
  let res = []
  let m = nums2.length
  let stack = []
  for(let i = 0; i < m; i++){
    //栈顶元素存在，并且当前的元素大于栈顶  
    while(stack.length && nums2[i] > stack[stack.length - 1]){
      map.set(stack.pop(), nums2[i]) 
    }  
    stack.push(nums2[i])
  }
  //栈内还有元素，说明后面没有比自己小的了
  while(stack.length){
    map.set(stack.pop(), -1)
  }
  nums1.forEach(item => {
    res.push(map.get(item))
  })
  return res
};

682. 棒球比赛

你现在是棒球比赛记录员。 给定一个字符串列表，每个字符串可以是以下四种类型之一： 1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。

2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
4. "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。

每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。 你需要返回你在所有回合中得分的总和。

方法一

常规做法，把各种情况列出来，再进行处理；

/**
 * @param {string[]} ops
 * @return {number}
 */
var calPoints = function(ops) {
    let res = []
    let opera = {
        '+': ()=>{
            let total = res.length > 1 ? Number(res[res.length - 1]) + Number(res[res.length - 2]) : res[0]
            res.push(total)
        },
        'D': () => {
            res.length && res.push(res[res.length - 1] * 2)
        },
        'C': () => {
            res.pop()
        },
        'in': e => {
            res.push(e)
        }
    }
    ops.forEach(e => {
        if(e in opera){
            opera[e]()
        }else {
            opera.in(e)
        }
    })
    return res.reduce((total, num) => Number(num) + Number(total))
};

Array。reduce(total, val, [index, arr])接受四个参数，前两个必须，后两个可选：

• total：初始值, 或者计算结束后的返回值；
• val：当前元素；
• index：当前元素的索引；
• arr：当前元素所属的数组对象；

方法二

攘外必先安内，先把内奸C和它同党，清除干净，在进行其他计算

/**
 * @param {string[]} ops
 * @return {number}
 */
var calPoints = function(ops) {
  for (let i = 0; i < ops.length; i++) {
    if (ops[i] === 'C') {
      //删除`c`和c前的一个元素
      ops.splice(i - 1, 2) 
      i -= 2
    }
  }
  let res = 0
  for(let i = 0; i < ops.length; i++){
    if(ops[i] === 'D'){
      //‘+’号是为了转换数据类型
      ops[i] = +(ops[i - 1] || 0) * 2
    } else if(ops[i] === '+') {
      ops[i] = +(ops[i - 1] || 0) + +(ops[i - 2] || 0)
    } 
    res += +ops[i]
  }
  return res
};

844. 比较含退格的字符串

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例

输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。

遍历字符串，使用一个栈存储符合要求的字符，然后再进行比较；

/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
function rebuild(str){
    let stack = []
    for(let e of str){
        if(e !== '#'){
            stack.push(e)
        }else{
            stack.pop()
        }   
    }
    return stack
};

var backspaceCompare = function(S, T) {
    return rebuild(S).join("") === rebuild(T).join("");
};

何时另外定义一个函数？？当主函数中需要多次调用某一操作时：

• 可能是传入不同参数；
• 也可能是需要多次执行同一函数；

1021. 删除最外层的括号

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

有点啰嗦，直接看示例

示例

输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

方法一

对于这种题目，通常都可以采用消消乐的思想：遍历字符串S

• 当第一次遇到(或者)时，不进行拼接，已在去掉最外层的()；注意除了去除最右边的)外，还要保证至少有一个(与之对应，所以c === ')' && opened -- > 1

• opened变量用于表示左（右）括号的数量，遍历时每遇到一个右（左）括号，该值就相应减一；

/**
 * @param {string} S
 * @return {string}
 */
var removeOuterParentheses = function(S) {
  let res = '';
  let opened = 0;
  for(let c of S) {
    if(c === '(' && opened ++ > 0) res += c;
    if(c === ')' && opened -- > 1) res += c;
  }
  return res;
};

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例

输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

思路

经典的使用栈解决问题的思路：

• 遍历数组；
• 根据具体要求，判断，是将当前遍历到的元素推进栈还是弹出栈顶元素；

/**
 * @param {string} S
 * @return {string}
 */
var removeDuplicates = function(S) {
    let stack = []
    for(let e of S){
        let stackTop = stack[stack.length - 1]
        if(stackTop === e){
            stack.pop()
        }else{
            stack.push(e)
        }
    }
    return stack.join("")
};

1441. 用栈操作构建数组

给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3..., n} 中依序读取一个数字。

请使用下述操作来构建目标数组 target ：

Push：从 list 中读取一个新元素， 并将其推入数组中。 Pop：删除数组中的最后一个元素。 如果目标数组构建完成，就停止读取更多元素。 题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

请返回构建目标数组所用的操作序列。

题目数据保证答案是唯一的。

示例

输入：target = [1,3], n = 3
输出：["Push","Push","Pop","Push"]
解释： 
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组，然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]

思路

• 先定义两个数组，分别存放操作字符串，和 最终数组；

• 遍历1~n，如何target没有包含当前遍历的元素，就往操作数组里push入栈和出栈两步操作；

• 否则往操作数组中push入栈操作，在最终数组中push该元素；

• 当最终数组于target数组长度相等后，停止遍历；

/**
 * @param {number[]} target
 * @param {number} n
 * @return {string[]}
 */
var buildArray = function(target, n) {
    let arr = [];
    let brr = [];
    for(let j = 1; j <= n; j++) {
        if(!target.includes(j)) {
            arr.push('Push');
            arr.push('Pop');
        } else {
            arr.push('Push');
            brr.push(j);
        }
        if(brr.length == target.length) {
            break;
        }
    }
    return arr;
};

1544. 整理字符串

给你一个由大小写英文字母组成的字符串 s 。

一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1] 不会同时满足下述条件：

• 0 <= i <= s.length - 2

• s[i] 是小写字符，但 s[i + 1] 是相同的大写字符；反之亦然 。

请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。

注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。

示例

输入：s = "leEeetcode"
输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode" 

示例2

输入：s = "abBAcC"
输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

思路

从左到右扫描字符串 s 的每个字符。扫描过程中，维护当前整理好的字符串，记为 ret。当扫描到字符 ch 时，有两种情况：

• 字符 ch 与字符串 ret 的最后一个字符互为同一个字母的大小写：根据题意，两个字符都要在整理过程中被删除，因此要弹出 ret 的最后一个字符；
• 否则：两个字符都需要被保留，因此要将字符 ch 附加在字符串 ret 的后面。

/**
 * @param {string} s
 * @return {string}
 */
var makeGood = function(s) {
    const len = s.length
    const res = []
    for(let val of s){
        let resTop = res[res.length - 1]
        if(res.length && 
           resTop !== val && 
           resTop.toLowerCase() === val.toLowerCase()){
            res.pop()
        }else {
            res.push(val)
        }
    }
    return res.join("")
};

Ⅱ排序

简单

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例

输入: s = "anagram", t = "nagaram"
输出: true

输入: s = "rat", t = "car"
输出: false

说明: 你可以假设字符串只包含小写字母。

思路

1.先将字符串转化为数组；

2.将数组进行排序；

3.比较两个数组；

var isAnagram = function (s, t) {
  if (s.length !== t.length) {
    return false
  }
  s = s.split('').sort().join('')
  t = t.split('').sort().join('')
  return s === t
};

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

思路

• filter过滤
• set去重

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    return [...new Set(nums1.filter((item)=>nums2.includes(item)))]
};

350. 两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2]
输出：[2]

说明：

• 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
• 我们可以不考虑输出结果的顺序。

与上一题不同的是，输出的结果元素个数与两个数组的最小长度相同

思路

• 遍历数组nums1，满足条件nums2.includes(val)后将该元素存起来；
• 并且在nums2中删除该元素；

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    let res = []
for(let e of nums1){
            if(nums2.includes(e)){
            res.push(e)
            nums2.splice(nums2.indexOf(e), 1)
        }
}
return res
};

922. 按奇偶排序数组 II

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

方法一

传统艺能，笨方法：

• 先将数组分为偶数部分和奇数部分；
• 遍历原数组，奇数索引时从奇数数组中添加最前面的元素到数组stack中，偶树索引同理；

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParityII = function(A) {
    let stack = []
    let odd = []
    let even = []
    for(let key in A){
        if(A[key]%2!==0){
            odd.push(A[key])
        }else{
            even.push(A[key])
        }
    }
    for(let key in A){
     if(key%2 === 0){
         stack[key] = even.shift()
     }else{
         stack[key] = odd.shift()
     }
 }
 return stack
};

方法二

思路

我们可能会被面试官要求写出一种不需要开辟额外空间的解法。

在这个问题里面，一旦所有偶数都放在了正确的位置上，那么所有奇数也一定都在正确的位子上。所以只需要关注 A[0], A[2], A[4], ... 都正确就可以了。

将数组分成两个部分，分别是偶数部分 even = A[0], A[2], A[4], ... 和奇数部分 odd = A[1], A[3], A[5], ...。定义两个指针 i 和 j, 每次循环都需要保证偶数部分中下标 i 之前的位置全是偶数，奇数部分中下标 j 之前的位置全是奇数。

算法

让偶数部分下标 i 之前的所有数都是偶数。为了实现这个目标，把奇数部分作为暂存区，不断增加指向奇数部分的指针，直到找到一个偶数，然后交换指针 i，j 所指的数。

var sortArrayByParityII = function(A) {
    let i = 0,
        j = 1;
    for(; i < A.length; i += 2){
        if(A[i] % 2 === 1){
        while(A[j] % 2 === 1)j += 2;
        [A[i],A[j]]=[A[j],A[i]];//ES6在引入了数组解构的概念，值互换会变得更加方便
        }
    }
    return A;
}

Ⅲ数组

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法一

笨蛋方法，暴力遍历：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let res = []
    for(let i = 0; i< nums.length; i++){
        for(let j = i + 1; j < nums.length; j++){
            if(target === nums[i] + nums[j]){
                res.push(i)
                res.push(j)
            }
        }
    }
    return res
};

方法二

解题思路

• 用 hashMap 存一下遍历过的元素和对应的索引。
• 每访问一个元素，查看一下 hashMap 中是否存在满足要求的目标数字。

写法一

const twoSum = (nums, target) => {
  // 存放出现过的数字，和对应的索引
  const prevNums = {};                         
  // 遍历元素
  for (let i = 0; i < nums.length; i++) {      
    // 当前元素
    const curNum = nums[i];                    
    // 满足题目要求的目标元素
    const targetNum = target - curNum;         
    // 在prevNums中找目标元素的索引
    const targetNumIndex = prevNums[targetNum];
    // 如果存在，直接返回 [目标元素的索引, 当前索引]
    if (targetNumIndex !== undefined) {        
      return [targetNumIndex, i];             
    }                                     
    // 如果不存在，说明之前没出现过目标元素
    // 每次都存入当前元素和对应的索引
    prevNums[curNum] = i;                      
  }
}

写法二

个人写法，有点晦涩

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map()
    for(let key in nums){
        targetNum = target - nums[key]
        if(map[targetNum]){
            return [map[targetNum], key]
        }
        else{
            map[nums[key]] = key
        }
    }
};

写法三：

精简版

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
  // 1. 构造哈希表
  const map = new Map(); // 存储方式 {need, index}

  // 2. 遍历数组
  for (let i = 0; i < nums.length; i++) {
    // 2.1 如果找到 target - nums[i] 的值
    if (map.has(nums[i])) {
      return [map.get(nums[i]), i];
    } else {
      // 2.2 如果没找到则进行设置
      map.set(target - nums[i], i);
    }
  }
};

**建议：**显然用Map替代对象字面量{}要好；

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

简单

Ⅳ字符串

简单