Array相关LeetCode题目笔记
11. 盛最多水的容器
题目描述：
代码语言：javascript复制给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2
提示：
n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解题思路：
代码语言：javascript复制一看题，最原始的方法，双层for循环遍历到ok，时间复杂度应该是O(n^2)。看官方和大佬解题思路，soga，关于Array类型的题要考虑到双指针，上代码：
class Solution {
public int maxArea(int[] height) {
//第一个指针，指向数组第一个数，也就是下标为0的数
int left = 0;
//第二个指针，指向数组最后一个数，为啥俩个指针要这样放嘞，因为这样他们的长度就是最长的，高度再论
int right = height.length - 1;
//假设最大面积为0，为啥嘞，防止height=[0]这样的数组出现
int maxArea = 0;
while (left < right) {//可以找出最大面积的条件
{
int area = Math.min(height[right], height[left]) * (right - left);
maxArea = Math.max(maxArea, area);
if (height[right] >= height[left]) {//谁的高度低，移动谁的指针
left;
} else {
--right;
}
}
}
return maxArea;
}
}
时间复杂度：O(n),空间复杂度O(1)283. 移动零
题目描述：
代码语言：javascript复制给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解题思路：
代码语言：javascript复制第一思路：循环，把非0的都循环出来放在另一个数组，最后再给它补上0。可实施。but人家不让拷贝额外的数组,删除它这个下标的元素？普通数组，初始化时大小就固定了，想念List，那就一个个移动下标，最坏从头移开始移动，时间复杂度O(n)。看题解，题解老哥脑回路niu
class Solution {
public void moveZeroes(int[] nums) {
//之后用j来记录非0元素下标
int j = 0;
for(int i = 0;i < nums.length;i ){
if(nums[i] != 0){//非0就记录它
nums[j ] = nums[i];//j 而不是 j是有原因的 这步等价于nums[j] = nums[i];j
}
}
//上面把非0的都移到前面了，开始补0操作，为啥不是i=j 1呢，因为上面的j 了
for(int i = j;i < nums.length;i ){
nums[i] = 0;
}
}
}
时间复杂度：O(n),空间复杂度O(1)70. 爬楼梯
题目描述：
代码语言：javascript复制假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解题思路：
代码语言：javascript复制第一思路：找规律
1个台阶：1 1种
2个台阶：1 1或2 2种
3个台阶：1 1 1、2 1、1 2 3种
4个台阶：1 1 1 1、2 1 1、1 2 1、1 2 1、2 2 5种
好像是斐波拉基数列，那就是f(n) = f(n-1) f(n-2),最差时间复杂度O(2^n)，注定超时啊，看题解后自己理解了下
class Solution {
public int climbStairs(int n) {
//只有1个台阶，直接返回1
if (n == 1) {
return 1;
}
//同上，直接返回2，为啥这么写，因为题目已经给出的
if (n == 2) {
return 2;
}
//为什么是n 1而不是n呢，因为此时的下标 1对应的才是台阶数，数组下标是从0开始的
int[] dp = new int[n 1];
//1个台阶和2个台阶已知，为啥没有dp[0]呢，因为题目说明是正整数
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < n 1; i ) {
dp[i] = dp[i - 1] dp[i - 2];
}
return dp[n];
}
}1. 两数之和
题目描述：
代码语言：javascript复制给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？解题思路：
代码语言：javascript复制第一思路：双层for循环
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; i) {
for (int j = i 1; j < n; j) {
if (nums[i] nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
时间复杂度：O(n^2)
于是有了另一个idea
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i ){
if(map.containsKey(target - nums[i])){
return new int[]{map.get(target-nums[i]),i};
}
map.put(nums[i],i);
}
return new int[0];
}
}
利用hashmap的key不能重复，完美。事件复杂度O(n)15. 三数之和
题目描述：
代码语言：javascript复制给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a b c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解题思路：
代码语言：javascript复制考虑的太多，想着可以参考俩数之和来搞，但是还得去重。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
int len = nums.length;
//判断空数组和数组长度小于3的，这种数组根本不符合描述
if(nums == null || len < 3){
return list;
}
//排好序，方便后续比较
Arrays.sort(nums);//事件复杂度O(NlogN)
//事件复杂度O(N)
for(int i = 0;i < len;i ){
//因为是排好序的数组，target都大于0了，那left right肯定大于0
if(nums[i] > 0){
break;
}
//排除重复的
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
int r = len - 1;
int l = i 1;
while (l < r){
int sum = nums[i] nums[r] nums[l];
if(sum == 0){
list.add(Arrays.asList(nums[i],nums[r],nums[l]));
//还是判断重复
while (l < r && nums[r] == nums[r - 1]){
r--;
}
while(l < r && nums[l] == nums[l 1]){
l ;
}
l ;
r--;
}
else if(sum > 0) {
r--;
}else {
l ;
}
}
}
return list;
}}
