双指针

283. 移动零

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        // 后面补 0
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

11. 盛最多水的容器

对应数字较小的那个指针以后不可能作为容器的边界了

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

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max_volume = 0;

        while (left < right) {
            // 先算当前面积
            int h = Math.min(height[left], height[right]);
            int w = right - left;
            int cur = h * w;

            max_volume = Math.max(max_volume, cur);

            // 再移动矮的一边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max_volume;
    }
}

三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n=nums.length;
        
        if (n<3)return new ArrayList<>();
        //List 是接口，不能直接 new，必须用 ArrayList 实现类
        //不管多复杂的泛型，右边永远只写：new ArrayList<>(),自动推断;
        List<List<Integer>>ans=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<n;i++){
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int left=i+1;
            int right=n-1;
            int twoSum=0-nums[i];
            while(left<right){
                if(nums[left]+nums[right]<twoSum){
                    left++;
                }else if(nums[left]+nums[right]>twoSum){
                    right--;
                }else{
                    // ans.add({nums[i],nums[left],nums[right]});
                    //
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));


                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;

                    left++;
                    right--;
                }
            }    
        }
    return ans;
    }
}

• Arrays.sort

• //List 是接口，不能直接 new，必须用 ArrayList 实现类
  //不管多复杂的泛型，右边只写：new ArrayList<>(),自动推断;
  

• 返回空，用return new ArrayList<>()

• 添加元素，

  1. 原生

  // 固定长度，不能 add/remove，**不能增删**
  List<Integer> item = Arrays.asList(a, b, c);
  

  2套一层可修改

  // 外面包 new ArrayList<>()
  List<Integer> item = new ArrayList<>(Arrays.asList(a, b, c));
  

• 快速把零散元素直接包装成一个 List

  ans.add( {x,y,z} ); // ❌ 语法报错
  ans.add(Arrays.asList(nums[i], nums[left], nums[right]));✅
  

42. 接雨水

class Solution {
    public int trap(int[] height) {
        int n=height.length;
        int ans=0;
        int left=0;
        int right=n-1;
        int leftMax=height[0];
        int rightMax=height[n-1];
        while(left<right){
            if(leftMax<rightMax){
                ans+=leftMax-height[left];
                left++;
                leftMax=Math.max(leftMax,height[left]);
            }
            else{
                ans+=rightMax-height[right];
                right--;
                rightMax=Math.max(rightMax,height[right]);
            }
        }
        return ans;    
    }
}

某一格子能接的水量= min(左边最高的墙，右边最高的墙)-该格子的高度

当 leftMax<rightMax时，左指针指向的柱子的存水量只取决于leftMax

当rightMax<leftMax时 ，右指针指向的柱子的存水量只取决于rightMax

谁的最大高度更小，谁就是「短板」，当前位置蓄水只由短板决定，所以必须先算短板这一侧、移动短板侧的指针。