Leetcode刷题记录_1
Leetcode
前言
考研初试结束之后，时间没有那么紧了，于是开始刷Leetcode了。
一方面是接触一下之前从未接触过的领域，另一方面也是为以后各种面试做一些准备。每天也不用多刷，平均拿出1h左右认真钻研透一道题就ok了。（佛系刷题hhh）
至于刷题顺序，由于我和小伙伴一起刷，她还没有学完数据结构，所以就先开始刷数组相关的题目，涉及到数据结构的东西会相对少一些。
目前准备是每刷5道题发一篇文章，以后可能会有调整。
正文
1. two sum
题目
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
学到的东西
这道题的暴力解法很容易想到，无非就是双重for循环遍历即可。
但是想要将时间复杂度降低到O(n) 属实是让我想了很久，最后的解决方法就是利用hash table查找的时间复杂度为O(1) 的特性，用空间换时间，抵消一个for循环，最后达成O(n)的时间复杂度。
在实现的时候，C语言的数组传参又有些忘记了：定义一个指针int * p = int[ ] a ; 然后传递p即可
2.Remove Duplicates from Sorted Array
题目
Given a sorted array, remove the duplicates in place such that each element appear only once
and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
学到的东西
这道题来来源于一个pdf文档，条件限制空间复杂度为O(1)。
该题需要设置一个index指针来过滤重复数值，只有当 num[index] !=num[i] 时，index++
4. Median of Two Sorted Arrays
题目
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
学到的东西
这是一道困难难度的题目，做完这一次之后我就决定以后先跳过所有困难的题目了。。。。
这道题还有一种更为通用的问法：求第K小的数。虽然我没有再去深究了。
这道题的问题所在就是要对两个数组进行一个合理的划分 ，如果左边数字的长度等于右边数字的长度：且左边的值都小于等于右边的值，那么边界四个数值的中位数即两个数组的中位数。 
在根据分割线左右四个元素调整时，要满足交叉小于关系：左上元素小于右下元素，左下小于右上。
可在第一个数组随机选择一个位置作为分割线位置(一般直接选择中间位置)，在另一个数组中进行二分查找来寻找合适的分割线位置
剩下的东西就不要太深究了，目前刚刚开始刷，还不太能完全理解及实现该算法。
11. Container With Most Water
题目
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
学到的东西
这道题是一个中等难度的题目，用到了一种双指针的思想，具体就是在数组两边分别定义 i 和 j， 每次将其中较小的一个向内移动(i++ or j–)。
其原理就是发现计算面积的规律：假设i和j分别指向的数值为4和9，那么i指向的4就已经达到了它可能达到面积值的最大值，原理如下：设i不动，j- -时：
a[j] > a[i]时， 水的高度不变， 宽减少， 故面积减少
a[j] < a[i]时， 水的高度减少， 宽减少， 故面积减少
综上所述，i指向的4已达到最大值， 故成立。
15. 3Sum
题目
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
Constraints:
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
学到的东西
这道题算是自己想出了解决方法，但是没有判断好时间复杂度是O(n2)还是O(n3)。
我使用时针分针秒针来类比该算法：首先将数组进行排序，对于有序数组，我们设置三个指针，最左边(最小值)的指针设为时针，左边的另一个指针设为分针， 最右边的指针设为秒针， 左边两个指针向右走， 最右边指针的向左走。和钟表一样，秒针遍历一遍分针才会动一下（实际就是for循环嵌套），以此类推。
最外层两个for循环即时针和分针的结束条件是遍历整个数组的有效部分， 而最内层即秒针的结束条件是sum < 0， 该条件与n无关故时间复杂度为O(1)。故由于停止条件的改变，时间复杂度也就从三层for循环变成了两层for循环+一个带有终止条件的while循环，时间复杂度也随之降了下来。
由于我一直都用C写程序，所以也该积累一些C++的使用方法了：
sort(nums.begin(), nums.end());//c++可以直接调用sort
vector<vector<int>> ans; //vector<int>是定义了一个list ，而两个vector可以理解成创建了一个二维数组
if (nums[second] + nums[third] == target) {
//类似于python的list.append ，这里直接输入宽度为3，长度为n的向量。
ans.push_back({nums[first], nums[second], nums[third]});
}