283. 移動零

給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。

請注意 ，必須在不復(fù)制數(shù)組的情況下原地對數(shù)組進(jìn)行操作。

示例 1:輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]
示例 2:輸入: nums = [0]
輸出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

進(jìn)階：你能盡量減少完成的操作次數(shù)嗎？

class Solution {
public void moveZeroes(int[] nums) {int n = nums.length;int slow = 0;int fast = 0;// 將非零元素前移while (fast < n) {if (nums[fast] != 0) {nums[slow] = nums[fast];slow++;}fast++;}// 將剩余元素置為零while (slow < n) {nums[slow] = 0;slow++;}
}}

思路：快慢指針

11. 盛最多水的容器

給定一個長度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。

找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

返回容器可以儲存的最大水量。

說明：你不能傾斜容器。

輸入：[1,8,6,2,5,4,8,3,7]
輸出：49 
解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍(lán)色部分）的最大值為 49。
示例 2：輸入：height = [1,1]
輸出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

class Solution {
public int maxArea(int[] height) {int left = 0;int right = height.length - 1;int maxArea = 0;while (left < right) {int area = Math.min(height[left], height[right]) * (right - left);maxArea = Math.max(maxArea, area);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
}
}

思路：雙指針法：頭尾指針，每次短的一端往中間靠近，（因為短的一端到另外一端已經(jīng)是最大容量）

15. 三數(shù)之和

給你一個整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請

你返回所有和為 0 且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

示例 1：輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。
示例 2：輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 。
示例 3：輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 。

要解決這個問題，可以使用雙指針的方法來找到和為0的三元組。首先，對數(shù)組進(jìn)行排序，然后固定一個數(shù)，使用雙指針在剩余的區(qū)間內(nèi)查找另外兩個數(shù)，使得三個數(shù)的和為0。

以下是解決該問題的具體步驟：

1、對數(shù)組進(jìn)行排序，以便于后續(xù)雙指針的操作。

2、遍歷排序后的數(shù)組，固定第一個數(shù) nums[i]：

• 若 nums[i] > 0，則說明后面的數(shù)都大于0，不可能存在和為0的三元組，直接返回結(jié)果。
• 若 i > 0 且 nums[i] == nums[i-1]，則說明當(dāng)前數(shù)與前一個數(shù)相同，為了避免重復(fù)的三元組，跳過當(dāng)前數(shù)。

3、使用雙指針解決剩下的兩數(shù)之和問題：

• 初始化左指針 left 為 i+1，右指針 right 為數(shù)組末尾索引。
• 在 left < right 的條件下，執(zhí)行以下操作：
  • 計算三個數(shù)的和 sum = nums[i] + nums[left] + nums[right]。
  • 若 sum == 0，則將三個數(shù)加入結(jié)果列表中，并移動指針 left 和 right，同時跳過重復(fù)的元素。
  • 若 sum > 0，則說明右指針指向的數(shù)較大，需要將右指針向左移動。
  • 若 sum < 0，則說明左指針指向的數(shù)較小，需要將左指針向右移動。

4、返回結(jié)果列表。

public class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();int n = nums.length;Arrays.sort(nums);for (int i = 0; i < n; i++) {if (nums[i] > 0) {break;}if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = n - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 跳過重復(fù)的元素while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;} else if (sum > 0) {right--;} else {left++;}}}return result;}
}

思路：定一移二

42. 接雨水

給定 n 個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍(lán)色部分表示雨水）。 
示例 2：輸入：height = [4,2,0,3,2,5]
輸出：9

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

public class Solution {public int trap(int[] height) {int left = 0;int right = height.length - 1;int maxLeft = 0;int maxRight = 0;int result = 0;while (left <= right) {if (height[left] <= height[right]) {if (height[left] >= maxLeft) {maxLeft = height[left];} else {result += maxLeft - height[left];}left++;} else {if (height[right] >= maxRight) {maxRight = height[right];} else {result += maxRight - height[right];}right--;}}return result;}
}