算法 1（数组、链表）

int[] res = new int[2];
// 数组的长度是 2
// - 第一个元素的下标是 0 (res[0])
// - 第二个元素的下标是 1 (res[1])

int[] nums = {5, 2, 9, 1, 5, 6};

// 1. 排序
Arrays.sort(nums); // [1, 2, 5, 5, 6, 9]

// 2. 查找 (必须先排序)
int index = Arrays.binarySearch(nums, 5); // 返回 2 或 3 (任意一个匹配项)

// 3. 转字符串打印
System.out.println(Arrays.toString(nums)); // 输出: [1, 2, 5, 5, 6, 9]

// 4. 填充
Arrays.fill(nums, 0); // [0, 0, 0, 0, 0, 0]

// 5. 数组转 List
// 注意陷阱，它返回的不是 java.util.ArrayList，而是 Arrays 类内部的一个私有静态类 ArrayList，如果需要可变的 List，请包裹一层
Integer[] boxed = {1, 2, 3};
List<Integer> list = Arrays.asList(boxed);
// list.set(0, 99); // OK: [99, 2, 3]
// list.add(4);     // 报错: UnsupportedOperationException (固定大小)

// 1. 基本用法
List<String> fruits = List.of("Apple", "Banana", "Orange");
System.out.println(fruits); // 输出: [Apple, Banana, Orange]

// 2. 尝试修改会报错
// fruits.add("Grape"); // 运行时抛出 UnsupportedOperationException

// 3. 传入 null 会报错
// List<String> listWithNull = List.of("Apple", null); // 运行时抛出 NullPointerException

// 4. 典型应用场景：定义常量列表
public static final List<String> DAYS_OF_WEEK = List.of("Mon", "Tue", "Wed", "Thu", "Fri");

public class ArrayList<E> {   //泛型E，因为表中要存的具体数据类型待定
    int capacity = 10;   //当前顺序表的容量
    int size = 0;   //当前已经存放的元素数量
    private Object[] array = new Object[capacity];   //底层存放数据的数组
}

public void add(E element, int index){   //插入方法需要支持在指定下标位置插入
    for (int i = size; i > index; i--)   //从后往前，一个一个搬运元素
        array[i] = array[i - 1];
    array[index] = element;   //腾出位置之后，直接插入元素放到对应位置上
    size++;   //插入完成之后，记得将size自增
}

public void add(E element, int index){
    if(index < 0 || index > size)    //插入之前先判断插入位置是否合法
        throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ "+size);
    for (int i = size; i > index; i--)
        array[i] = array[i - 1];
    array[index] = element;
    size++;
}

public void add(E element, int index){
    if(index < 0 || index > size)
        throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ "+size);
    if(capacity == size) {
        int newCapacity = capacity + (capacity >> 1);   //扩容规则就按照原本容量的1.5倍来吧
        Object[] newArray = new Object[newCapacity];    //创建一个新的数组来存放更多的元素
        System.arraycopy(array, 0, newArray, 0, size);   //使用arraycopy快速拷贝原数组内容到新的数组
        array = newArray;   //更换为新的数组
        capacity = newCapacity;   //容量变成扩容之后的
    }
    for (int i = size; i > index; i--)
        array[i] = array[i - 1];
    array[index] = element;
    size++;
}

public String toString() {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < size; i++) builder.append(array[i]).append(" ");
    return builder.toString();
}

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < 20; i++)
        list.add(i, i);
    System.out.println(list);
}

@SuppressWarnings("unchecked")   //屏蔽未经检查警告
public E remove(int index){   //删除对应位置上的元素，注意需要返回被删除的元素
    E e = (E) array[index];   //因为存放的是Object类型，这里需要强制类型转换为E
    for (int i = index; i < size; i++)   //从前往后，挨个往前搬一位
        array[i] = array[i + 1];
    size--;    //删完记得将size--
    return e;
}

@SuppressWarnings("unchecked")
public E remove(int index){
    if(index < 0 || index > size - 1)
        throw new IndexOutOfBoundsException("删除位置非法，合法的插入位置为：0 ~ "+(size - 1));
    E e = (E) array[index];
    for (int i = index; i < size; i++)
        array[i] = array[i + 1];
    size--;
    return e;
}

@SuppressWarnings("unchecked")
public E get(int index){
    if(index < 0 || index > size - 1)   //在插入之前同样要进行范围检查
        throw new IndexOutOfBoundsException("非法的位置，合法的位置为：0 ~ "+(size - 1));
    return (E) array[index];   //直接返回就完事
}

public int size(){   //获取当前存放的元素数量
    return size;
}

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyArrayList<E> {
    // 真正存储数据的底层数组
    private E[] data;
    // 记录当前元素个数
    private int size;
    // 默认初始容量
    private static final int INIT_CAP = 1;

    public MyArrayList() {
        this(INIT_CAP);
    }

    public MyArrayList(int initCapacity) {
        data = (E[]) new Object[initCapacity];
        size = 0;
    }

    // 增
    public void addLast(E e) {
        int cap = data.length;
        // 看 data 数组容量够不够
        if (size == cap) {
            resize(2 * cap);
        }
        // 在尾部插入元素
        data[size] = e;
        size++;
    }

    public void add(int index, E e) {
        // 检查索引越界
        checkPositionIndex(index);

        int cap = data.length;
        // 看 data 数组容量够不够
        if (size == cap) {
            resize(2 * cap);
        }

        // 搬移数据 data[index..] -> data[index+1..]
        // 给新元素腾出位置
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        // 插入新元素
        data[index] = e;

        size++;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    // 删
    public E removeLast() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
        int cap = data.length;
        // 可以缩容，节约空间
        if (size == cap / 4) {
            resize(cap / 2);
        }

        E deletedVal = data[size - 1];
        // 删除最后一个元素
        // 必须给最后一个元素置为 null，否则会内存泄漏
        data[size - 1] = null;
        size--;

        return deletedVal;
    }

    public E remove(int index) {
        // 检查索引越界
        checkElementIndex(index);

        int cap = data.length;
        // 可以缩容，节约空间
        if (size == cap / 4) {
            resize(cap / 2);
        }

        E deletedVal = data[index];

        // 搬移数据 data[index+1..] -> data[index..]
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }

        data[size - 1] = null;
        size--;

        return deletedVal;
    }

    public E removeFirst() {
        return remove(0);
    }

    // 查
    public E get(int index) {
        // 检查索引越界
        checkElementIndex(index);

        return data[index];
    }

    // 改
    public E set(int index, E element) {
        // 检查索引越界
        checkElementIndex(index);
        // 修改数据
        E oldVal = data[index];
        data[index] = element;
        return oldVal;
    }

    // 工具方法
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    // 将 data 的容量改为 newCap
    private void resize(int newCap) {
        E[] temp = (E[]) new Object[newCap];

        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }

        data = temp;
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }


    // 检查 index 索引位置是否可以存在元素
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }


    // 检查 index 索引位置是否可以添加元素
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    private void display() {
        System.out.println("size = " + size + " cap = " + data.length);
        System.out.println(Arrays.toString(data));
    }


    public static void main(String[] args) {
        // 初始容量设置为 3
        MyArrayList<Integer> arr = new MyArrayList<>(3);

        // 添加 5 个元素
        for (int i = 1; i <= 5; i++) {
            arr.addLast(i);
        }

        arr.remove(3);
        arr.add(1, 9);
        arr.addFirst(100);
        int val = arr.removeLast();

        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i));
        }
    }

}

left=0, right=nums.length-1;
while(left<=right){//left=right还是合法区间，所以要包含=的情况
    middle=(left+right)/2;//这样写可能导致整数溢出，应该按照下面的写法
    if(nums[middle]>target)
        right=middle-1;//左闭右闭，下一次搜索的区间包含right所在位置数值，而我们已经确定middle不是target，所以可以right可以进一步缩减至target-1
    else if(nums[middle]<target)
        left=middle+1;
    else
        return middle;
}
return -1

public int search(int[] nums, int target) {
    // 避免当 target 小于nums[0]或大于nums[nums.length - 1]时多次循环运算
    if (target < nums[0] || target > nums[nums.length - 1]) {
        return -1;
    }
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int middle = left + ((right - left) >> 1);
        if (nums[middle] > target) {
            return middle-1;
        }
        else if (nums[middle] < target) {
            left = middle + 1;
        }
        else { // nums[middle] = target
            return middle;
        }
    }
    // 未找到目标值
    return -1;
}

left=0, right=num.length;
while(left<right){//left=right不是合法区间，所以不包含=的情况
    middle=(left+right)/2;
    if(num[middle]>target)
        right=middle;//左闭右开，下一次搜索的区间不包含right所在位置数值，而我们已经确定middle不是target，所以right可以设置为middle
    else if(num[middle]<target)
        left=middle+1;
    else
        return middle;
}
return -1

public int search(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else { // nums[mid] > target
            right = mid;
        }
    }
    // 未找到目标值
    return -1;
}

// 左闭右闭
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;
    int left = 0;
    int right = m * n - 1;
    while (left <= right) {
        int mid = left + (right-left)/2;
        int x = matrix[mid / n][mid % n];
        if (x == target) {
            return true;
        }
        else if (x < target) {
            left = mid+1;
        } else {
            right = mid-1;
        }
    }
    return false;
}

// 左闭右闭
public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 未找到目标值
    return left;
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        // 数组为空或者所有数都<target或所有数都>target
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1}; // nums 中没有 target
        }
        // 如果 start 存在，那么 end 必定存在
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }
    // 左闭右闭
    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

// 左闭右闭
public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    //【⚠️注意】当 left == right 时，我们就找到了答案，不需要再进入循环，所以 while 循环条件是 left<right
    while (left < right) {
        int mid = (left + right) >>> 1;
        // 【核心逻辑】与最右侧元素比较
        if (nums[mid] > nums[nums.length - 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    // 循环结束时 left == right，即为最小值下标
    return nums[right];
}

// 全部用左闭右闭
class Solution {
    public int search(int[] nums, int target) {
        // 1. 找到旋转点（最小值的下标）
        int i = findMin(nums);
        // 2. 判断 target 在哪一段有序区间
        // (1) target 只可能在第一段 [0, i-1]
        if (target > nums[nums.length - 1]) {
            return search(nums, 0, i - 1, target); // 注意：如果 i 为 0，说明数组未旋转或旋转了一圈，此时右边界为 -1，区间无效
        } else { // (2) target 只可能在第二段 [i, n-1]
            return search(nums, i, nums.length - 1, target);
        }
    }


    // 二分寻找旋转排序数组中最小值的下标（153）
    private int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[nums.length - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    // 二分查找（704）
    private int search(int[] nums, int left, int right, int target) {
        // 边界检查：如果区间本身就不合法（例如左 > 右），直接返回 -1
        if (left > right) return -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }
        return -1;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int last = nums[n - 1]; // 参照物：最后一个元素
        int left = 0;
        int right = n - 1;
        while (left <= right) { // 闭区间不为空
            int mid = left + (right - left) / 2;
            int x = nums[mid];
            if (x == target) {
                return mid;
            }
            // 1、mid 在右侧有序段
            if (x <= last) {
                // target 也在右侧有序段，且在 mid 右边
                if (target <= last && target > x) left = mid + 1;
                // target 也在右侧有序段，且在 mid 左边；或者 target 在左侧有序段，还是在 mid 左边
                else right = mid - 1;
            } else { // 2、mid 在左侧有序段
                // target 也在左侧有序段，且在 mid 左边
                if (target > last && target < x) right = mid - 1;
                // target 也在左侧有序段，且在 mid 右边；或者 target 在右侧有序段，还是在 mid 右边
                else left = mid + 1;
            }
        }
        return -1;
    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int size=nums.length; //数组只能覆盖元素，不能删除元素，因此数组的大小nums.length始终不变，为了后面的循环不再考虑尾部空出的元素，因此对用size作为循环的限制，并在每次覆盖一个元素后使size-1
        for(int i=0;i<size;i++){
            if(nums[i]==val){
                for(int j=i+1;j<size;j++){
                    nums[j-1]=nums[j];
                }
                i--; //因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--;
            }
        }
        return size;
    }
}

while (list.contains(Integer.valueOf(2))) {
    list.remove(Integer.valueOf(2));
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0; //慢指针
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) { //快指针
            if (nums[fastIndex] != val) {
                nums[slowIndex++] = nums[fastIndex]; //这里用slowIndex++简化了代码
            }
        }
        return slowIndex;
    }
}

class Solution {
  public void moveZeroes(int[] nums) {
    if(nums==null) {
      return;
    }
    //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
    int j = 0;
    for(int i=0;i<nums.length;i++) {
      if(nums[i]!=0) {
        nums[j++] = nums[i];
      }
    }
    //非0元素统计完了，剩下的都是0了
    //所以第二次遍历把末尾的元素都赋为0即可
    for(int i=j;i<nums.length;i++) {
      nums[i] = 0;
    }
  }
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int i=0, j=nums.length-1;
        int[] result=new int[nums.length];
        int k=result.length-1;
        while(i<=j){
            if(nums[i]*nums[i]<nums[j]*nums[j]){
                result[k--]=nums[j]*nums[j];
                j--;
            }else{
                result[k--]=nums[i]*nums[i];
                i++;
            }
        }
        return result;
    }
}

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ?
                Math.max(res, (j - i) * height[i++]): // i是短板
                Math.max(res, (j - i) * height[j--]);  // j是短板
        }
        return res;
    }
}

//   相当于
class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int res = 0;
        while (i < j) {
            res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) {
                i++; // 左边短，左指针右移
            } else {
                j--; // 右边短（或相等），右指针左移
            }
        }
        return res;
    }
}

public void sortColors(int[] nums) {
    int n = nums.length;
    int ptr = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[i] == 0) {
            int temp = nums[i];
            nums[i] = nums[ptr];
            nums[ptr] = temp;
            ++ptr;
        }
    }
    for (int i = ptr; i < n; ++i) {
        if (nums[i] == 1) {
            int temp = nums[i];
            nums[i] = nums[ptr];
            nums[ptr] = temp;
            ++ptr;
        }
    }
}

public void sortColors(int[] nums) {
    int n = nums.length;
    int p0 = 0, p1 = 0;
    for (int i = 0; i < n; ++i) {
        if (nums[i] == 1) {
            int temp = nums[i];
            nums[i] = nums[p1];
            nums[p1] = temp;
            ++p1;
        } else if (nums[i] == 0) {
            int temp = nums[i];
            nums[i] = nums[p0];
            nums[p0] = temp;
            if (p0 < p1) {
                temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
            }
            ++p0;
            ++p1;
        }
    }
}