穹灵科技

11. 盛*多水的容器（JS实现）

1 题目
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳*多的水。

2 思路
该题使用首尾双指针向中间靠拢的办法，逐步比较面积大小

3代码
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
var low = 0;
var high = height.length – 1;
var max = Math.min(height[low], height[high]) * (high – low);

while(low < high) {
if (height[low] < height[high]) {
low++;
} else {
high–;
}

max = Math.max(max, Math.min(height[low], height[high]) * (high – low));
}
return max;
};

15. 三数之和（JS实现）

1 题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

2 思路
这道题参考了题解，利用了排序 + 双指针 + 散列表去重，折腾了一晚上

3代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
var result = [];
var map = {};
var value;
var left, right;
var sum;
nums.sort(function(a,b){
return a-b;
});

if (nums[0] > 0 || nums[nums.length-1] < 0) return result;

for (var i=0; i<nums.length; i++){
left = i+1;
right = nums.length – 1;
while(left < right) {
sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
var key = ” + nums[i] + nums[left] + nums[right];
if (!map[key]) result.push([nums[i], nums[left], nums[right]]);
map[key] = true;
left++;
right–;
} else if (sum < 0){
left++;
} else {
right–;
}
}
}

return result;
};

16. *接近的三数之和（JS实现）

1 题目
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target *接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target *接近的三个数的和为 2. (-1 + 2 + 1 = 2).

2 思路
这道题还是利用了排序 + 双指针的方法解决

3代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
if (nums.length <= 3) {
return nums.reduce(function(prev, curr){
return prev + curr;
});
}
nums.sort(function(a, b){
return a-b;
})

var left,right;
var diff = target – nums[0] – nums[1] – nums[2];
var sum;

for (var i=0; i<nums.length; i++) {
left = i + 1;
right = nums.length – 1;
while(left < right) {
sum = nums[i] + nums[left] + nums[right]
if (Math.abs(diff) > Math.abs(target – sum)) { //注意这里对比的是*对值
diff = target – sum;
}
if (diff === 0) return target; //相加等于target，此时直接返回
if (target – sum > 0) {
left++;
} else {
right–;
}
}
}

return target – diff;
};

18. 四数之和（JS实现）

1 题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

2 思路
这道题还是利用了排序 + 双指针 + 散列表去重的方法解决，与三数之和相比多加了一层循环

3代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
if (nums.length < 4) return [];
nums.sort(function(a,b){
return a-b;
});

var map = {};
var result = [];
var sum;
var key;
var filterMap = {};
for (var i=0; i<nums.length-3; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;

var min = nums[i] + nums[i+1] + nums[i+2] + nums[i+3];
if (min > target) break; //*小的四个数加起来都太大，那么久彻底没戏了

var max = nums[i] + nums[nums.length-1] + nums[nums.length-2] + nums[nums.length-3];
if (max < target) continue; //当前数加上其余*大的三个数，仍然比较小，那么说明当前数太小了

for (var j=i+1; j<nums.length-2; j++) {
var left = j + 1;
var right = nums.length – 1;

while(left < right) {
sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum === target) {
key = ” + nums[i] + nums[j] + nums[left] + nums[right];
if (!map[key]) {
result.push([nums[i], nums[j], nums[left], nums[right]]);
map[key] = true;
}
left++;
right–;
} else if (sum > target) {
right–;
} else {
left++;
}
}
}
}

return result;
};

22. 括号生成（JS实现）

1 题目
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

2 思路
这道题利用树的构造方法来枚举可能的情况，在枚举的过程进行剪枝操作，每个叶子节点就是*后的有效结果。注意生成过程中，表达式中左括号的数量始终小于等于右括号

3代码
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
function node(str, left, right) {
this.val = str;
this.leftChild = null;
this.rightChild = null;
this.left = left; //还剩余左括号的数量
this.right = right; //还剩余右括号的数量
}

function traverse(treeNode, result) {
let {left, right, val} = treeNode;

if (left === 0 && right === 0) { //括号用完，推入结果
result.push(val);
return;
}

if (left === 0 && right > 0) { //左括号用完，只能加右括号
treeNode.rightChild = new node(val + ‘)’, left, right – 1);
traverse(treeNode.rightChild, result);
return;
}

if (left === right) { //当前剩余的左括号和右括号数量相等，则新括号必须为左括号
treeNode.leftChild = new node(val + ‘(‘, left – 1, right);
traverse(treeNode.leftChild, result);
return;
}

if (left < right) { //其余情况既可以添加左括号，又可以添加右括号
treeNode.leftChild = new node(val + ‘(‘, left – 1, right);
traverse(treeNode.leftChild, result);
treeNode.rightChild = new node(val + ‘)’, left, right -1);
traverse(treeNode.rightChild, result);
}
}

const root = new node(‘(‘, n-1, n);
const result = [];
traverse(root, result);
return result;
};