认识数组

数组是最基础的一种数据结构，无论是什么样的算法题，大部分都会涉及到对数组的操作。如何有效的利用数组，并且在数组上运用各种算法进行题目求解，是我们学习的目标。常见的基于数组的问题有排序、二分查找、双指针、滑动窗口以及模拟。

三数之和

力扣题目链接
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

  • 核心 1 在于如何去除重复：排序后跳过相同的数字。
  • 核心 2 在于如何去除不必要的计算：nums[i] 大于 0，就结束跳出。
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> List = new ArrayList<List<Integer>>();
        if (nums.length < 3)
            return List;
        Arrays.sort(nums); // 进行排序
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0)
                break; // nums[i]大于0，则三数之和大于0，所以结束跳出
            if (i > 0 && nums[i] == nums[i - 1])
                continue; // 去掉重复
            for (int j = i + 1, k = nums.length - 1; j < k;) {
                int res = nums[i] + nums[j] + nums[k];
                if (res == 0) {
                    List.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (j < k && nums[j] == nums[j + 1])
                        j++; // 去掉左重复
                    while (j < k && nums[k] == nums[k - 1])
                        k--; // 去掉右重复
                    j++;
                    k--;
                } else if (res < 0)
                    j++;
                else if (res > 0)
                    k--;
            }
        }
        return List;
    }
}

最接近的三数之和

力扣题目链接
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。

  • 与三数之和思想基本一致，仍然是固定左侧，右侧用双指针搜索，避免三层嵌套循环
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                    closestSum = sum;
                }
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    return sum;
                }
            }
        }
        return closestSum;
    }
}

最大子数组和

力扣题目链接
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  • 每加一次，记录当前和，当前和比 ans 大，则更新
  • 若当前和小于等于 0，则必须丢弃，设置当前和为 0，继续往后加
class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int sum = 0;
        if (nums.length == 1) {
            return nums[0];
        }
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum > ans) {
                ans = sum;
            }
            if (sum <= 0) {
                sum = 0;
            }
        }
        return ans;
    }
}

合并区间

力扣题目链接
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

  • 如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾
  • 否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

二分查找

力扣题目链接
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        //闭区间
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

移除元素

力扣题目链接
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

  • 双指针，left 用于修改元素，right 用于找到所有不等于 val 的数字
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

有序数组的平方

力扣题目链接
给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

  • 双指针，左右分别指向数组两端，谁的平方大就把谁加进去
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                i++;
            } else {
                ans[pos] = nums[j] * nums[j];
                j--;
            }
            pos--;
        }
        return ans;
    }
}

长度最小的子数组

力扣题目链接
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

  • 滑动窗口，其实也是用到了双指针的思想
  • 窗口内的总和小于 target，则右侧指针后移，反之左侧指针后移
  • 直到右侧指针走到数组终点
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= target) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;

        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

螺旋矩阵

力扣题目链接
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

  • 按要求模拟即可，定义行、列的边界，并在每次填充后向内收缩
class Solution {
    public int[][] generateMatrix(int n) {
        int l = 0, r = n - 1, t = 0, b = n - 1;
        int[][] ans = new int[n][n];
        int num = 1, tar = n * n;
        while (num <= tar) {
            for (int i = l; i <= r; i++) {
                ans[t][i] = num++;
            }
            t++;
            for (int i = t; i <= b; i++) {
                ans[i][r] = num++;
            }
            r--;
            for (int i = r; i >= l; i--) {
                ans[b][i] = num++;
            }
            b--;
            for (int i = b; i >= t; i--) {
                ans[i][l] = num++;
            }
            l++;
        }
        return ans;
    }
}

缺失的第一个正数

力扣题目链接
给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

  • 这个未出现的正整数一定在 1 与 nums.length 之间
  • 原地哈希，将所有 1 与 nums.length 之间的正整数 n 与 nums[n-1] 上的数字进行交换
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

除自身以外数组的乘积

力扣题目链接
给你一个整数数组 nums，返回数组 answer。其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

  • 分别计算每个元素的前缀乘积与后缀乘积，最后将他们乘起来
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // 用于存储最终结果的数组
        int[] answer = new int[n];
        // 计算前缀乘积
        int prefixProduct = 1;
        for (int i = 0; i < n; i++) {
            // 先将当前位置的前缀乘积存入结果数组
            answer[i] = prefixProduct;
            // 更新前缀乘积
            prefixProduct *= nums[i];
        }
        // 计算后缀乘积并与前缀乘积相乘
        int suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            // 将当前位置的后缀乘积乘到结果数组对应位置上
            answer[i] *= suffixProduct;
            // 更新后缀乘积
            suffixProduct *= nums[i];
        }
        return answer;
    }
}

按奇偶排序数组

力扣题目链接
给定一个非负整数数组 nums，nums 中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当 nums[i] 为奇数时，i 也是奇数；当 nums[i] 为偶数时，i 也是偶数。

  • 两次遍历，一次遍历找出所有的偶数，放入下标为偶数的索引；另一次遍历找出所有的奇数，放入下标为奇数的索引
class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int i = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                ans[i] = x;
                i += 2;
            }
        }
        i = 1;
        for (int x : nums) {
            if (x % 2 == 1) {
                ans[i] = x;
                i += 2;
            }
        }
        return ans;
    }
}

最长连续序列

力扣题目链接
给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

  • 排序后考察每个元素与前一个元素的差值
class Solution {
    public int longestConsecutive(int[] nums) {
        // 处理数组为空的情况
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 对数组进行排序
        Arrays.sort(nums);
        int res = 1; // 初始化最长连续序列长度为 1
        int len = 1; // 当前连续序列长度初始化为 1
        for (int i = 1; i < nums.length; i++) {
            // 跳过重复元素
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            // 如果当前元素比前一个元素大 1，说明是连续序列
            if (nums[i] == nums[i - 1] + 1) {
                len++;
            } else {
                // 连续序列中断，更新最长连续序列长度
                res = Math.max(res, len);
                // 重置当前连续序列长度
                len = 1;
            }
        }
        // 处理最后一个连续序列
        res = Math.max(res, len);
        return res;
    }
}

将有序数组转换为二叉搜索树

力扣题目链接
给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

  • 递归思路，每次二分查找的中间位置则是根节点
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length);
    }
    public TreeNode dfs(int[] nums, int left, int right) {
        if (left == right) {
            return null;
        }
        int m = (left + right) >>> 1;
        return new TreeNode(nums[m], dfs(nums, left, m), dfs(nums, m + 1, right));
    }
}

存在重复元素Ⅱ

力扣题目链接
给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，满足 nums[i] == nums[j] 且 abs(i - j) <= k。如果存在，返回 true；否则，返回 false。

  • 正常模拟即可，两重循环搜索
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= i + k && j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

汇总区间

力扣题目链接
给定一个无重复元素的有序整数数组 nums。返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x。

  • 一次遍历，当相邻元素差值不为1时，便找到了一个区间
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<String>();
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int low = i;
            i++;
            while (i < n && nums[i] == nums[i - 1] + 1) {
                i++;
            }
            int high = i - 1;
            StringBuilder str = new StringBuilder(Integer.toString(nums[low]));
            if (low < high) {
                str.append("->");
                str.append(Integer.toString(nums[high]));
            }
            res.add(str.toString());
        }
        return res;
    }
}

寻找重复数

力扣题目链接
给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个重复的整数，返回这个重复的数。你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

  • 核心是弗洛伊德判圈算法，与之类似的题目还有环形链表。具体的步骤是使用快慢指针，慢指针一次移动一步，快指针一次移动两步
  • 如果存在环，则二者一定会相遇。并且相遇时，让快指针保持在相遇点，让慢指针重新指向开始位置，二者每次都移动一步。当它们再次相遇时，这个相遇点就是环的入口节点
class Solution {
    public int findDuplicate(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return -1;
        }
        if (nums.length == 2) {
            return nums[0];
        }
        int fast = 0, slow = 0;
        do {
            fast = nums[nums[fast]];
            slow = nums[slow];
        } while (fast != slow);
        slow = 0;
        do {
            slow = nums[slow];
            fast = nums[fast];
        } while (fast != slow);
        return fast;
    }
}

最长连续序列

力扣题目链接
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

  • O(n) 的算法，说明大概率用到哈希表，所以我们把所有的数字放在哈希表中，就能做到 O(1) 的查询效率
  • 对于哈希表中的每一个数字 x，首先判断哈希表中是否存在 x - 1，若存在，则跳过 x，因为 x 此时已不可能是最长连续序列的起点
  • 对于满足条件的 x，从 x + 1 开始，依次向上寻找直到断掉
class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int ans = 0;
        for (int num : nums) {
            set.add(num);
        }
        for (int temp : set) {
            if (set.contains(temp - 1)) {
                continue;
            }
            int y = temp + 1;
            while (set.contains(y)) {
                y++;
            }
            ans = Math.max(ans, y - temp);
        }
        return ans;
    }
}

移动0

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。

  • 用指针记录零元素的边界
class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[left] = nums[i];
                left++;
            }
        }
        for (int j = left; j < nums.length; j++) {
            nums[j] = 0;
        }
    }
}

盛最多水的容器

给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

  • 优先移动短板策略
class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        while (left <= right) {
            int temp = (right - left) * Math.min(height[left], height[right]);
            ans = Math.max(ans, temp);
            if (height[right] > height[left]) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
}

接雨水

力扣题目链接
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

  • 维护下标 i 及其左侧的位置中的最大高度
  • 维护下标 i 及其右侧的位置中的最大高度
  • 最终的答案是左右侧较小的最大高度减去当前高度之和
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if (height.length == 0) {
            return 0;
        }
        int[] leftMax = new int[len];
        leftMax[0] = height[0];
        for (int i = 1; i < len; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
        }
        int[] rightMax = new int[len];
        rightMax[len - 1] = height[len - 1];
        for (int j = len - 2; j >= 0; j--) {
            rightMax[j] = Math.max(height[j], rightMax[j + 1]);
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

和为K的子数组

力扣题目链接
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。

  • 前缀和的思想，先用一次遍历存下前缀和，之后可以在 O(1) 时间内计算出区间内子数组的和
  • 子数组问题常用前缀和
class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        int[] flag = new int[len + 1];
        flag[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            flag[i + 1] = flag[i] + nums[i];
        }
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {
                if (flag[right + 1] - flag[left] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

下一个排列

力扣题目链接
给你一个整数数组 nums，找出 nums 的下一个排列。整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 从后往前找第一个升序对，这个升序对的第一个数字是需要交换的
  • 从后往前找第一个大于升序对的第一个数字的数字，这个数字应该与升序对的第一个数字进行交换
  • 交换后，后面位置的数字可以被证明为是正好逆序的，所以使用 left 和 right 指针两两交换，变为升序即可
  • 对于没有字典序更大的排列的排列，会直接跳到 left 与 right 指针交换那一步
class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

颜色分类

力扣题目链接
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums,原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。

  • 看到原地修改数组，则用一个指针维护修改边界即可
  • 用交换的思想防止把数组的值覆盖掉
class Solution {
    public void sortColors(int[] nums) {
        int point = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[point];
                nums[point] = temp;
                point++;
            }
        }
        for (int i = point; i < nums.length; i++) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[point];
                nums[point] = temp;
                point++;
            }
        }
    }
}

多数元素

力扣题目链接
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

  • 排序后最中间那个元素就是多数元素
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

只出现一次的数字

给你一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

  • a 和 a 异或运算为 0
  • 0 和 a 异或运算为 a
  • 所以全部异或，最后的结果就是答案
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
}

数组中的第K个最大元素

力扣题目链接
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

  • 优先队列（小顶堆），里面保存 K 个数字
  • 比堆顶元素大，就存进去，到最后是最大的 K 个数字
  • 则堆顶是第 K 个最大元素
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        for (int num : nums) {
            if (queue.size() < k) {
                queue.offer(num);
            } else if (num > queue.peek()) {
                queue.poll();
                queue.offer(num);
            }
        }
        return queue.peek();
    }
}

前K个高频元素

力扣题目链接
给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

  • map 存数字以及出现的频率
  • 根据 map.keySet() 建立小顶堆（重写排序逻辑）
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (int num : map.keySet()) {
            if (queue.size() < k) {
                queue.offer(num);
            } else if (map.get(num) > map.get(queue.peek())) {
                queue.poll();
                queue.offer(num);
            }
        }
        int[] ans = new int[k];
        int i = 0;
        while (queue.size() != 0) {
            ans[i] = queue.poll();
            i++;
        }
        return ans;
    }
}

滑动窗口最大值

力扣题目链接
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

  • 设置双端队列存储最大值，队列降序排列，一轮遍历，先把窗口塞满，然后这时就可以返回最大值（队头）了，但返回前要做两件事，首先，要加入数组当前下标到队尾，并保证是单调的，其次，如果队头这是已经到了窗口左边，就移除队头
  • 遍历的 i 是尾部数字的索引，i + 1 - k 是头部数字的索引，若队列头部的索引已经比 i + 1 - k 小，则 poll
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.offerLast(i);
            if (queue.peek() < i + 1 - k) {
                queue.poll();
            }
            if (i + 1 >= k) {
                res[i + 1 - k] = nums[queue.peek()];
            }
        }
        return res;
    }
}

轮转数组

力扣题目链接
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

  • 先整体反转，再反转前 k 个，最后反转其他的
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

除自身以外数组的乘积

力扣题目链接
给你一个整数数组 nums，返回数组 answer,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

  • 一个数组保存前缀积，另一个数组保存后缀积
  • 答案是对应位置的前缀后缀乘积
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n];
        pre[0] = 1;
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        int[] suf = new int[n];
        suf[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = pre[i] * suf[i];
        }
        return ans;
    }
}

矩阵置0

力扣题目链接
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

  • 用矩阵的第一行和第一列记录该行该列是否有 0，即对于每一个数字 matrix[i][j]，判断其对应的首行首列位置是否有 0，若有，则把该数置为 0
  • 再设置两个标志位用于判断首行首列原本是否有 0，因为若原本有 0，则需要将首行首列全部置 0
  • 能够利用第一行和第一列进行标记的核心原因是：若矩阵当中有 0，则首行首列是一定会被修改的
class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean rowFlag = false;
        boolean colFlag = false;
        for (int i = 0; i < col; i++) {
            if (matrix[0][i] == 0) {
                rowFlag = true;
                break;
            }
        }
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                colFlag = true;
                break;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowFlag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (colFlag) {
            for (int j = 0; j < row; j++) {
                matrix[j][0] = 0;
            }
        }
    }
}

搜索二维矩阵

力扣题目链接
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。

  • 从右上角元素开始搜索，即定义 i = 0，j = matrix[0].length - 1
  • 若该元素比目标值大，则消去该元素所在列，即 j–
  • 若该元素比目标值小，则消去该元素所在行，即 i++
  • 当 i 和 j 越界时，则查找失败
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        while (i <= matrix.length - 1 && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}

旋转图像

力扣题目链接
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

  • 先水平轴翻转，再主对角线翻转（和脑筋急转弯没啥区别）
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}