Array相关LeetCode题目笔记
11. 盛最多水的容器
-
题目描述：
给你 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 -
解题思路：
一看题，最原始的方法，双层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. 移动零
-
题目描述：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/move-zeroes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 -
解题思路：
第一思路：循环，把非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. 爬楼梯
-
题目描述：
假设你正在爬楼梯。需要 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 -
解题思路：
第一思路：找规律 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. 两数之和
-
题目描述：
给定一个整数数组 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) 的算法吗？ -
解题思路：
第一思路：双层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. 三数之和
-
题目描述：
给你一个包含 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 -
解题思路：
考虑的太多，想着可以参考俩数之和来搞，但是还得去重。 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; }
}
评论区