成都市网站备案,wordpress页面是什么,海螺集团网站建设招标公告,网站充值支付宝收款怎么做解题思路#xff1a;
初始化指针#xff1a; 左指针指向数组起始位置#xff0c;右指针指向数组末尾。计算当前面积#xff1a; 左右指针相遇前所围成的矩形面积。更新最大面积#xff1a; 比较当前面积与已知最大面积。移动指针#xff1a; 移动较高指针无法获得更…
解题思路
初始化指针 左指针指向数组起始位置右指针指向数组末尾。计算当前面积 左右指针相遇前所围成的矩形面积。更新最大面积 比较当前面积与已知最大面积。移动指针 移动较高指针无法获得更大面积故移动较低指针。
Java代码
class Solution {public int maxArea(int[] height) {int l 0, r height.length - 1;int ans 0;while (l r) {int area Math.min(height[l], height[r]) * (r - l);ans Math.max(ans, area);if (height[l] height[r]) {l;} else {r--;}}return ans;}
}复杂度分析
时间复杂度 严格O(n)最多移动 n 次指针。空间复杂度 所有额外使用的空间与输入规模无关空间复杂度为O (1)。 解题思路
排序 首先对数组进行排序便于后续处理重复元素和双指针操作。遍历数组 使用外层循环遍历数组固定第一个元素 nums[i]。双指针法 对于每个固定的 nums[i]使用双指针 j左指针和 k右指针在剩余数组中寻找两个数使得三数之和为0。跳过重复元素 外层循环中若当前元素与前一个元素相同则跳过避免重复的三元组。内层循环中找到有效三元组后跳过所有与当前指针值相同的元素防止重复。
Java代码
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();if (nums null || nums.length 3) return result;Arrays.sort(nums);for (int i 0; i nums.length - 2; i) {if (i 0 nums[i] nums[i - 1]) continue;int j i 1;int k nums.length - 1;while (j k) {int sum nums[i] nums[j] nums[k];if (sum 0) {j;} else if (sum 0) {k--;} else {result.add(Arrays.asList(nums[i], nums[j], nums[k]));while (j k nums[j] nums[j 1]) j;while (j k nums[k] nums[k - 1]) k--;j;k--;}}}return result;}
}复杂度分析
时间复杂度 排序时间复杂度为 O(nlogn)遍历与双指针外层循环遍历 O(n) 次内层双指针遍历 O(n) 次总时间复杂度为 O( n 2 n^2 n2)。空间复杂度 主要用于存储结果列表最坏情况下空间复杂度为 O( n 2 n^2 n2)平均情况下为 O(1) 至 O(n)。
