1. 283 移動零
鏈接：題目鏈接
題解：
要求：時間復雜度 < O (n^2)
題解：將非零元素依次往前移（占據0元素的位置），最后再將0元素填充至數組尾。時間復雜度O(n)，用一個指針x來維護非零元素的起始位置，在用一個指針y從左到右遍歷元素（跳過0元素），將y指針下標元素填充至x指針下標，x指針與y指針均往后移，填充完非零元素后，x指針往后移動，填充0元素。
代碼：
public void moveZeroes(int[] nums) {if (nums.length == 1) {return;}int len = nums.length;int zeroLeftIndex = 0;for (int i = 0; i < len; ++i) {if (nums[i] != 0) {nums[zeroLeftIndex] = nums[i];zeroLeftIndex++;}}for (int i = zeroLeftIndex; i < len; ++i) {nums[i] = 0;}}
2. 11 盛最多水的容器
鏈接：題目鏈接
題解：
要求：時間復雜度 <= O(n logn)
題解：容納水公式：(r - l) * Math.min(height[l], height[r])，假設答案區間為[l, r]，則要排除掉[l, r]子區間容水量，因為(r - l)子區間只會變得更小，所以僅當子區間Math.min(height[l], height[r])變大才有可能擴大容水量，才有可能容納更多的水，那么我們需要把這類情況依次排除掉，所以這里要用到雙指針，分別在區間左右兩端，往內收讓Math.min(height[l], height[r])變大（當height[r] > height[l]時，移動r指針是沒用的，必須移動l指針），維護一個maxValue(最大容水量)。[l, r]父區間一樣的考慮方法，所以需要把[l, r]擴至最大區間[0, height.length -1]。時間復雜度O(n)
代碼：
public int maxArea(int[] height) {int len = height.length - 1;int l = 0, r = len;int maxValue = (r - l) * Math.min(height[l], height[r]);while(l < r) {if (height[l] < height[r]) {l ++;} else {r --;}maxValue = Math.max((r - l) * Math.min(height[l], height[r]), maxValue);}return maxValue;}
3. 15 三數之和
鏈接：題目鏈接
題解：
要求：時間復雜度 <= O(n^2)
題解：這里可以枚舉前兩個數字（需要先排序，保證不重復枚舉），第三個數字可以通過 num = - (num[i] + num[j])計算得到，通過hash能O(1)時間復雜度判斷是否存在該值。還需要注意去重，這里用Set去重。時間復雜度O(n^2)。
代碼：
public List<List<Integer>> threeSum(int[] nums) {// 先對數組進行排序// 左右指針 枚舉 前兩個數字 相同數字最多出現一次(先右指針往右移 再枚舉左指針往右移)// hashMap存儲每個數組 對應出現的次數Set<List<Integer>> result = new HashSet<>();Arrays.sort(nums);Map<Integer, Integer> numCountMap = new HashMap<>();for (int num: nums) {numCountMap.put(num, numCountMap.getOrDefault(num, 0) + 1);}int len = nums.length;for (int i = 0; i < len; ) {for (int j = i + 1; j < len; ) {int target = -1 * (nums[i] + nums[j]);int repeatTargetCount = 0;if (nums[i] == target) {repeatTargetCount++;}if (nums[j] == target) {repeatTargetCount++;}Integer targetCount = numCountMap.getOrDefault(target, 0);if (targetCount > repeatTargetCount) {List<Integer> threeSum = Arrays.asList(nums[i], nums[j], target);Collections.sort(threeSum);result.add(threeSum);}do {j++;} while (j < len && nums[i] == nums[j]);}do {i++;} while (i < len && nums[i - 1] == nums[i]);}return new ArrayList<>(result);}4. 42 接雨水
鏈接：題目鏈接
題解：
要求：時間復雜度 <= O(nlogn)
題解：考慮第i列能接到多少水，只需要考慮 i列 左邊最大高度 maxL 右邊最大高度 maxR 取 Max(0, min(maxL, maxR) - nums[i])。左邊指針往右走 邊走邊維護maxL。maxR 怎么維護? 右指針往左走 維護單調棧，單調棧 如果左邊的高度 小于 單調棧內的高度 就不入棧 棧元素(下標, 高度)。遍歷左指針時 如果下標 小于 指針下標 就出棧。時間復雜度O(n)
代碼：
public int trap(int[] height) {// 考慮第i列 只需要考慮 i列 左邊最大高度 maxL 右邊最大高度 maxR 取 Max(0, min(maxL, maxR) - nums[i])// 左邊指針往右走 邊走邊維護maxL// maxR 怎么維護? 右指針往左走 維護單調棧// 單調棧 如果左邊的高度 小于 單調棧內的高度 就不入棧 棧元素(下標, 高度)// 遍歷左指針時 如果下標 小于 指針下標 就出棧int len = height.length - 1;if (len == 0) {return 0;}Stack<Integer> stack = new Stack<>();for (int r = len; r >= 0; -- r) {if (stack.isEmpty()) {stack.push(r);} else if (height[stack.peek()] < height[r]) {stack.push(r);}}int maxL = height[0];int ans = 0;for (int i = 1; i < len; ++ i) {while (stack.peek() <= i) {stack.pop();} ans += Math.max(0, Math.min(maxL, height[stack.peek()]) - height[i]);maxL = Math.max(maxL, height[i]);}return ans;}如果對你有幫助，辛苦點個贊，謝謝啦，朋友！！！
)
