leetcode from 20/04/2021

腾讯

数组与字符串

1、两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

暴力破解。hashmap的得看看

2、寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。

粗暴合并两个数组然后找出中位数
nums1.insert(nums1.end(),nums2.begin(), nums2.end()
注意数组类型是int，要注意类型转换再做除法

3、最长回文子串

substr的用法忘了。第一位是起始，第二表示往后第几个字符

递归思想，且注意考虑好边界情况。搞一个矩阵来判断回文串的长度。
左右指的元素不等直接false，如果两头相等且中间只剩一个元素或者无则必为回文；否则则取决于中间的字符串是否为回文串。最后返回起始位置和回文串长度

4、字符串转换整数（atoi）

• 忽略前导空格
• 确定正负号
• 检查输入是否合法，是否有溢出风险等

5 、最长公共前缀

第一想法就是纵向比较（一列一列的来）外层循环横向移动第一个字符串换字符，里层按行移动到不同的字符串；如果字符不相等了或者长度不够了就跳出循环。

6、三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

个人觉得难点在于如何降低复杂度，保证【不重复】的三元组。get了双指针的思路。可以先排序，同时注意如果遇到相同元素应该要跳过。

7、最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

和上一题思路很像，但是我考虑的特殊情况全部白搭，完全可以走程序解决。注意最里层循环才是扫描到最后一个数字的，同时要注意最后的和可能比target小也可能大。

8、有效的括号

这题思路比较简单，遇到左括号就把相应的右括号压栈；遇到右括号就pop看看相不相等，最后看看栈是否为空。

9、删除排序数组中的重复项

已经排序，遇到重复的元素跳过即可并记录个数，同时把后面的赋值给前面的。

10、盛最多水的容器

毫无修饰的暴力破解果然超时了。双指针上线，向着不会更差的方向移动，每次移动height较小的那个。

24日下午三点记录以上，20号下午临时回家有点打乱节奏。这段时间没啥事觉得可以刷刷题，目前的小感想：很多题目思路不难，但是真正实现复杂度问题和临界状况还是蛮恼人的。题目要多见，才会知道更多的解题方法。比如目前双指针我就get啦！