数组

这场景下通常是要求必须在数组中原位操作

数组去重

26. 删除有序数组中的重复项 easy

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.

• 返回 k 。 Return k.

跟移动零有点类似, 快慢指针, 慢指针跟快指针比较, 如果不同, 在慢指针的下一个位置填入

class Solution {
    public int removeDuplicates(int[] nums) {
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == nums[idx]) continue;
            nums[++idx] = nums[i];
        }
        return idx + 1;
    }
}

消除元素

735. 行星碰撞 mid

LCR 037. 行星碰撞

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

解法 栈

正只影响它右边的负数, 负只影响它左边的正数
遍历每个元素, 判断能否消除左侧元素以及能否存在

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int e : asteroids) {
            if (e > 0) {
                stack.addLast(e);
                continue;
            }
            int pre;
            boolean uneq = true; // 不相等
            while (!stack.isEmpty() && (pre = stack.getLast()) > 0 && pre <= -e) {
                stack.removeLast();
                if (pre == -e) {
                    uneq = false;
                    break;
                }
            }
            if (uneq && (stack.isEmpty() || stack.getLast() < 0)) stack.addLast(e);
        }
        return stack.stream().mapToInt(o -> o).toArray();
    }
}

循环数组

189. 轮转数组 mid

剑指 Offer 58 - II. 左旋转字符串

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

整体反转, 左侧反转, 右侧反转

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    public void reverse(int[] nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

区间内的元素和

238. 除自身以外数组的乘积 mid

剑指 Offer 66. 构建乘积数组

给你一个整数数组 nums，返回 数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

解法 1 前缀积

正序在[i]位保存前[i-1]位的积; 然后倒序, 用一个变量保存后缀积
O(1)空间复杂度

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int pre = 1;
        for (int i = 0; i < n; i++) {
            res[i] = pre;
            pre *= nums[i];
        }
        int suf = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= suf;
            suf *= nums[i];
        }
        return res;
    }
}

303. 区域和检索 - 数组不可变 easy

给定一个整数数组 nums，处理以下类型的多个查询:

• 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
• 实现 NumArray 类： NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

前缀和

class NumArray {

    private int[] sum;

    public NumArray(int[] nums) {
        this.sum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
    }

    public int sumRange(int left, int right) {
        return sum[right + 1] - sum[left];
    }
}

724. 寻找数组的中心下标 easy

1991
LCR 012. 寻找数组的中心下标

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        for (int i = n - 2; i >= 0; i--) {
            arr[i] = arr[i + 1] + nums[i + 1];
        }
        int sum = 0;
        int res = -1;
        for (int i = 0; i < n; i++) {
            if (sum == arr[i]) return i;
            sum += nums[i];
        }
        return res;
    }
}

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int res = -1;
        int pre = 0;
        for (int i = 0; i < n; i++) {
            if (sum - nums[i] == pre * 2) return i;
            pre += nums[i];
        }
        return res;
    }
}

数组中找环

565. 数组嵌套 mid

索引从 0 开始长度为 N 的数组 A，包含 0 到 N-1 的所有整数。找到最大的集合 S 并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } 且遵守以下的规则:

假设选择索引为 i 的元素 A[i] 为 S 的第一个元素，S 的下一个元素应该是 A[A[i]]，之后是 A[A[A[i]]]... 以此类推，不断添加直到 S 出现重复的元素。

解法

细看是找最大环
由元素范围可知没有重复, 每个元素的入度不超过 1

class Solution {
    public int arrayNesting(int[] nums) {
        int res = 0, n = nums.length;
        boolean[] visit = new boolean[n];
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            // 这里用 i, 结束时还会停留在原位置
            while (!visit[i]) {
                visit[i] = true;
                i = nums[i];
                ++cnt;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }
}