盛最多水的容器，三数之和 ，有效的括号

盛最多水的容器：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

1. 使用双层循环暴力求解，但是会超过时间限制，放弃此方法
2. 使用双指针

双指针： 从左右两边开始计算面积，底边长在求解的过程中逐渐减小，所以应用较高的线来寻找较长的范围，从而获得较大的面积。因此当左值较小时，左指针增加，右值较小时，右指针减小。

var maxArea = function(height) {
        let max = 0
        let left = 0
        let right = height.length-1
        while(left<right){
            let area = Math.min(height[left],height[right])*(right-left)
            max = area>max?area:max
            height[left]>height[right]?right--:left++
        }
    
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12

三数之和：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解答方式：排序加双指针，这道题的难点在于如何去除重复的解 ， 但其实经过一次排序之后，只需要判断本次循环的值是否与上一次的值相等，相等就跳过 。 循环过程和指针移动的过程都需要去重！
时间复杂度：数组排序：O（nlogn）循环O（n）双指针遍历O（n）总：O（nlogn）+O（n）*O（n）=O（n2）

var threeSum = function (nums) {
    let newarr = [...new Set(nums)]
    if(newarr[0]===0&&newarr.length==1)
    return [[0,0,0]]

    nums.sort((a, b) => a - b)
    let result = []
    let arr = new Map()
    for (let i = 0; i < nums.length; i++) {
        let flag = false
        arr.has(nums[i]) ? flag = true : arr.set(nums[i])
        if (flag) {
            continue
        }
        //设置好左右指针
        let left = i + 1
        let right = nums.length - 1
        while (left < right) {
            if (nums[left] + nums[right] + nums[i] === 0) {
                result.push([nums[i],nums[left], nums[right]])
                //还要对左右指针进行去重
                while(nums[left]==nums[left+1]){
                left++
                }
                while(nums[right]==nums[right-1]){
                right--
                }
            }
            if (nums[left] + nums[right] + nums[i] >= 0) {
                right--
            }
            if (nums[left] + nums[right] + nums[i] < 0) {
                left++
            }
        }
    }
    return result
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

有效的括号 :

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
1
2
3

解题方法： 遇到左符号就进栈，遇到右符号判断一下是否跟当前栈顶元素相等，相等就出栈，不相等就返回false，最后判断栈是否为空

/**
 * @param {string} s
 * @return {boolean}
 */

 var isValid = function(s) {
    if(s.length<=1){
        return false
    }
    if(s.charAt(0)===')'||s.charAt(0)===']'||s.charAt(0)==='}'){
        return false
    }

    //想了一下，遇到左符号就进栈，遇到右符号就出栈，最后判断栈是否为空
    const map = new Map([
        ['(',')'],
        ['[',']'],
        ['{','}']
    ])
    let arr = []
    for(let i of s){
        //左符号就进栈
        if(map.has(i)){
            arr.push(map.get(i))
        }
        //遇到右符号判断一下是否跟当前栈顶元素相等
        //相等就出栈
        else if(arr[arr.length-1]===i){
            arr.pop()
        }
        //不相等就返回false
        else{
            return false
        }
    }
    return arr.length===0?true:false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37