移动0

感觉算是简单题，但是一时没想出来。
思路其实就是两步：第一步把非0的数字全挤到左边，同时要记录序列的末尾（用第二个指针），第二步把序列末尾到数组结尾的这一区间全部填。

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length <= 1) return;
        int cur = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0){ // 不等于0就填左边
                nums[cur] = nums[i];
                cur++;
            }
        }
        for(; cur < nums.length; cur++){
            nums[cur] = 0;
        }
        return;
    }
}

盛水最多的容器

感觉有一点点思路，但是不清晰。看题解：
在初始时，左右指针分别指向数组的左右两端，每次迭代移动一个高度较小的指针。
感觉思路挺简单的，一开始想不出来不应该。

class Solution {
    public int maxArea(int[] height) {
        int res = 0;
        int left = 0;
        int right = height.length - 1;
        while(left < right){
            int h = Math.min(height[left], height[right]);
            res = Math.max(res, h * (right - left));
            // 三目运算符 需要赋值
            int dummy = height[left] > height[right] ? right-- : left++;
        }
        return res;
    }
}

三数之和

第一个版本，错误，只过了几个用例就超出时间限制，二分写的不对。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> s = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            for(int j = nums.length - 1; j > i; j--){
                int k = (i + j) / 2;
                while(k != i && k != j){
                    int sum = nums[k] + nums[i] + nums[j];
                    if(sum == 0){
                        s.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        break;
                    }
                    else if(sum > 0){ // 说明k偏大了
                        k--;
                    }else{
                        k++;
                    }
                }
            }
        }
        return new ArrayList<>(s);
    }
}

GPT4o的二分法，过了100%用例

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> s = new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            // 跳过重复的元素
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 在剩余数组中进行二分查找
            for (int j = i + 1; j < nums.length - 1; j++) {
                int target = -(nums[i] + nums[j]);
                // 使用二分查找来查找合适的k
                int left = j + 1, right = nums.length - 1;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (nums[mid] == target) {
                        s.add(Arrays.asList(nums[i], nums[j], nums[mid]));
                        break;
                    } else if (nums[mid] < target) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
        }
        return new ArrayList<>(s);
    }
}

真正的官方做法应该是排序+双指针。
因为题解容忍的时间复杂度能够达到On²，首先将数组排序，便于处理。
之后，可以从左往右移动i，并且在“i到nums.length“区间内，寻找另外两个数，记为l与r，l与r相向移动，过程中仍然需要注意去重。这个的解法时间复杂度更低。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        if(nums == null || len < 3) return res;
        // 排序
        Arrays.sort(nums);
        for(int i = 0; i < len; i++){
            // 数组排序了 如果i也大于0 就没必要考虑后面的了
            if(nums[i] > 0) break;
            
            //去重
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1;
            int r = len - 1;
            // 比较的就是 i, l, r三数 i需要固定 l和r可以变动
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum == 0){
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 继续去重
                    while(l < r && nums[l] == nums[l + 1]) l++;
                    while(l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }else if(sum < 0){
                    l++;
                }else if(sum > 0){
                    r--;
                }
            }
        }
        return res;
    }
}