插入和删除O(1)哈希表能做到，随机访问就要用数组了，维护一个双索引

java
class RandomizedSet {

    private Map<Integer, Integer> valToIndexMap;
    private List<Integer> nums;
    private Random random;

    public RandomizedSet() {
        valToIndexMap = new HashMap<>();
        nums = new ArrayList<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (valToIndexMap.containsKey(val)) {
            return false;
        }
        valToIndexMap.put(val, nums.size());
        nums.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!valToIndexMap.containsKey(val)) {
            return false;
        }
        int index = valToIndexMap.get(val);
        int lastVal = nums.get(nums.size() - 1);
        nums.set(index, lastVal);
        valToIndexMap.put(lastVal, index);
        valToIndexMap.remove(val);
        nums.remove(nums.size() - 1);
        return true;
    }

    public int getRandom() {
        return nums.get(random.nextInt(nums.size()));
    }

}

类似的还有LRU,保证插入删除O(1)还要数据有序

双指针

java
class Solution {
    public int[] twoSum(int[] numbers, int target) {
                int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                // 返回的下标是从1开始的，所以需要加1
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++; // 如果和小于目标数，移动左指针
            } else {
                right--; // 如果和大于目标数，移动右指针
            }
        }
        return new int[]{-1, -1}; // 如果没有找到，返回-1
    }
}

一道模拟题，需要懂点脑子，重要的就是标记

生命细胞

java
class Solution {
     public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) return;

        int m = board.length;
        int n = board[0].length;

        // 遍历面板中的每个细胞
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 计算周围活细胞的数量
                int liveNeighbors = countLiveNeighbors(board, i, j, m, n);

                // 根据活细胞周围活细胞的数量更新细胞状态
                if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    // 活细胞周围活细胞少于2个或超过3个，该细胞死亡
                    board[i][j] = 2;
                } else if (board[i][j] == 0 && liveNeighbors == 3) {
                    // 死细胞周围正好有3个活细胞，该细胞复活
                    board[i][j] = 3;
                }
            }
        }

        // 将临时状态转换回0或1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 2) { //死了
                    board[i][j] = 0;
                } else if (board[i][j] == 3) { //复活
                    board[i][j] = 1;
                }
            }
        }
    }

    // 计算给定细胞周围的活细胞数量
    private int countLiveNeighbors(int[][] board, int i, int j, int m, int n) {
        int liveNeighbors = 0;
        for (int x = Math.max(0, i - 1); x <= Math.min(m - 1, i + 1); x++) {
            for (int y = Math.max(0, j - 1); y <= Math.min(n - 1, j + 1); y++) {
                if (x == i && y == j) continue; // 跳过自身
                if (board[x][y] == 1 || board[x][y] == 2) {
                    liveNeighbors++;
                }
            }
        }
        return liveNeighbors;
    }

}

也是矩阵类的题目，是这样的，慢慢处理

先处理第一行和第一列标记是否有0这里不需要都遍历找到一个就得清零，所以剪枝，

接下来就是从第一行第一列开始检查，用第一行第一列标记需不需要清零，最后根据前面标记的第一行第一列来决定是否清零，还得检查刚开始标记的第一行行第一列

java
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;

        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRowZero = false;
        boolean firstColZero = false;

        // 检查第一行和第一列是否包含0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // 使用第一行和第一列来标记哪些行和列需要被置为0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // 根据标记来置0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 根据记录来决定是否将第一行和第一列置为0
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}