LeetCode 解题思路 3（Hot 100）

解题思路：

1. 初始化指针： 左指针指向数组起始位置，右指针指向数组末尾。
2. 计算当前面积： 左右指针相遇前所围成的矩形面积。
3. ​更新最大面积： 比较当前面积与已知最大面积。
4. ​移动指针： 移动较高指针无法获得更大面积，故移动较低指针。

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)。

解题思路：

1. ​排序： 首先对数组进行排序，便于后续处理重复元素和双指针操作。
2. ​遍历数组： 使用外层循环遍历数组，固定第一个元素 nums[i]。
3. 双指针法： 对于每个固定的 nums[i]，使用双指针 j（左指针）和 k（右指针）在剩余数组中寻找两个数，使得三数之和为0。
4. 跳过重复元素：
   • 外层循环中，若当前元素与前一个元素相同，则跳过，避免重复的三元组。
   • 内层循环中，找到有效三元组后，跳过所有与当前指针值相同的元素，防止重复。

Java代码：

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> 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$)。
• 空间复杂度： 主要用于存储结果列表，最坏情况下空间复杂度为 O($n^2$)，平均情况下为 O(1) 至 O(n)。