解法

思路和算法

整数 $n$ 反转的结果为 $\textit{reverse}(n)$，计算 $|n - \textit{reverse}(n)|$ 即可。

计算 $\textit{reverse}(n)$ 的方法为：从低到高遍历整数 $n$ 的每一位，将每一位根据遍历顺序从高到低填入反转后的数字。

代码

###Java

class Solution {
    public int mirrorDistance(int n) {
        return Math.abs(n - reverse(n));
    }

    public int reverse(int n) {
        int reversed = 0;
        while (n != 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }
        return reversed;
    }
}

###C#

public class Solution {
    public int MirrorDistance(int n) {
        return Math.Abs(n - Reverse(n));
    }

    public int Reverse(int n) {
        int reversed = 0;
        while (n != 0) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }
        return reversed;
    }
}

###C++

class Solution {
public:
    int mirrorDistance(int n) {
        return abs(n - reverse(n));
    }

    int reverse(int n) {
        int reversed = 0;
        while (n) {
            reversed = reversed * 10 + n % 10;
            n /= 10;
        }
        return reversed;
    }
};

###Python

class Solution:
    def mirrorDistance(self, n: int) -> int:
        def reverse(n: int) -> int:
            reversed = 0
            while n:
                reversed = reversed * 10 + n % 10
                n //= 10
            return reversed
        return abs(n - reverse(n))

###C

int reverse(int n) {
    int reversed = 0;
    while (n) {
        reversed = reversed * 10 + n % 10;
        n /= 10;
    }
    return reversed;
}

int mirrorDistance(int n) {
    return abs(n - reverse(n));
}

###Go

func mirrorDistance(n int) int {
    return abs(n - reverse(n))
}

func abs(n int) int {
    if n >= 0 {
        return n
    } else {
        return -n
    }
}

func reverse(n int) int {
    reversed := 0
    for n != 0 {
        reversed = reversed * 10 + n % 10
        n /= 10
    }
    return reversed
}

###JavaScript

var mirrorDistance = function(n) {
    return Math.abs(n - reverse(n));
};

var reverse = function(n) {
    let reversed = 0;
    while (n) {
        reversed = reversed * 10 + n % 10;
        n = Math.floor(n / 10);
    }
    return reversed;
};

###TypeScript

function mirrorDistance(n: number): number {
    return Math.abs(n - reverse(n));
};

function reverse(n: number): number {
    let reversed = 0;
    while (n) {
        reversed = reversed * 10 + n % 10;
        n = Math.floor(n / 10);
    }
    return reversed;
};

复杂度分析

• 时间复杂度：$O(\log_{10} n)$，其中 $n$ 是给定的数字。整数 $n$ 的位数是 $O(\log_{10} n)$，需要遍历整数 $n$ 的每一位。

• 空间复杂度：$O(1)$。

解法

思路和算法

当三个不同下标 $i$、$j$ 和 $k$ 组成有效三元组时，三个下标的任意排列对应的有效三元组的距离都是相等的，因此可以规定 $i < j < k$，则有效三元组的距离是 $|i - j| + |j - k| + |k - i| = (j - i) + (k - j) + (k - i) = 2(k - i)$。为了计算有效三元组的最小距离，需要计算 $2(k - i)$ 的最小可能值。

遍历数组 $\textit{nums}$，使用哈希表记录每个元素值对应的下标列表，从左到右遍历数组 $\textit{nums}$ 即可确保每个元素值对应的下标列表按升序排序。

得到每个元素值对应的下标列表之后，对于每个元素值，遍历其下标列表，计算该元素的有效三元组的最小可能距离。对于下标列表中的任意三个元素 $i$、$j$ 和 $k$，其中 $i < j < k$，这三个元素对应数组 $\textit{nums}$ 中的三个不同下标且组成有效三元组，其距离为 $2(k - i)$。为了计算最小距离，应考虑下标列表中的每组三个相邻元素，其中的最大值与最小值之差的两倍即为该有效三元组的距离，遍历下标列表中的所有由三个相邻元素组成的有效三元组之后即可得到当前元素值的有效三元组的最小距离。对于所有元素值分别计算有效三元组的最小距离之后，即可得到数组 $\textit{nums}$ 的有效三元组的最小距离。

如果一个元素在数组 $\textit{nums}$ 中的出现次数少于三次，则该元素不存在有效三元组。如果所有元素在数组 $\textit{nums}$ 中的出现次数都少于三次，则数组 $\textit{nums}$ 中不存在有效三元组，答案是 $-1$。

代码

###Java

class Solution {
    public int minimumDistance(int[] nums) {
        int minDistance = Integer.MAX_VALUE;
        Map<Integer, List<Integer>> numToIndices = new HashMap<Integer, List<Integer>>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            numToIndices.putIfAbsent(nums[i], new ArrayList<Integer>());
            numToIndices.get(nums[i]).add(i);
        }
        Set<Map.Entry<Integer, List<Integer>>> entries = numToIndices.entrySet();
        for (Map.Entry<Integer, List<Integer>> entry : entries) {
            List<Integer> indices = entry.getValue();
            int size = indices.size();
            for (int i = 2; i < size; i++) {
                int distance = (indices.get(i) - indices.get(i - 2)) * 2;
                minDistance = Math.min(minDistance, distance);
            }
        }
        return minDistance != Integer.MAX_VALUE ? minDistance : -1;
    }
}

###C#

public class Solution {
    public int MinimumDistance(int[] nums) {
        int minDistance = int.MaxValue;
        IDictionary<int, IList<int>> numToIndices = new Dictionary<int, IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            numToIndices.TryAdd(nums[i], new List<int>());
            numToIndices[nums[i]].Add(i);
        }
        foreach (KeyValuePair<int, IList<int>> pair in numToIndices) {
            IList<int> indices = pair.Value;
            int size = indices.Count;
            for (int i = 2; i < size; i++) {
                int distance = (indices[i] - indices[i - 2]) * 2;
                minDistance = Math.Min(minDistance, distance);
            }
        }
        return minDistance != int.MaxValue ? minDistance : -1;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要遍历数组将每个元素的下标列表存入哈希表，然后需要遍历哈希表计算有效三元组的最小距离，每次遍历的时间都是 $O(n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。哈希表的空间是 $O(n)$。

解法一

思路和算法

当三个不同下标 $i$、$j$ 和 $k$ 组成有效三元组时，三个下标的任意排列对应的有效三元组的距离都是相等的，因此可以规定 $i < j < k$，则有效三元组的距离是 $|i - j| + |j - k| + |k - i| = (j - i) + (k - j) + (k - i) = 2(k - i)$。

数组 $\textit{nums}$ 的长度是 $n$。遍历 $0 \le i < j < k < n$ 的所有三元组 $(i, j, k)$，当 $\textit{nums}[i] = \textit{nums}[j] = \textit{nums}[k]$ 时，三元组 $(i, j, k)$ 是有效三元组，其距离是 $2(k - i)$，使用该距离更新有效三元组的最小距离。遍历结束之后即可得到数组 $\textit{nums}$ 的有效三元组的最小距离。

如果数组 $\textit{nums}$ 中不存在三个不同下标的元素相等，则数组 $\textit{nums}$ 中不存在有效三元组，答案是 $-1$。

代码

###Java

class Solution {
    public int minimumDistance(int[] nums) {
        int minDistance = Integer.MAX_VALUE;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] == nums[i]) {
                    for (int k = j + 1; k < n; k++) {
                        if (nums[k] == nums[j]) {
                            int distance = (k - i) * 2;
                            minDistance = Math.min(minDistance, distance);
                        }
                    }
                }
            }
        }
        return minDistance != Integer.MAX_VALUE ? minDistance : -1;
    }
}

###C#

public class Solution {
    public int MinimumDistance(int[] nums) {
        int minDistance = int.MaxValue;
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] == nums[i]) {
                    for (int k = j + 1; k < n; k++) {
                        if (nums[k] == nums[j]) {
                            int distance = (k - i) * 2;
                            minDistance = Math.Min(minDistance, distance);
                        }
                    }
                }
            }
        }
        return minDistance != int.MaxValue ? minDistance : -1;
    }
}

复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要遍历的三元组个数是 $O(n^3)$。

• 空间复杂度：$O(1)$。

解法二

思路和算法

见题解「3741. 三个相等元素之间的最小距离 II」。

代码

###Java

class Solution {
    public int minimumDistance(int[] nums) {
        int minDistance = Integer.MAX_VALUE;
        Map<Integer, List<Integer>> numToIndices = new HashMap<Integer, List<Integer>>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            numToIndices.putIfAbsent(nums[i], new ArrayList<Integer>());
            numToIndices.get(nums[i]).add(i);
        }
        Set<Map.Entry<Integer, List<Integer>>> entries = numToIndices.entrySet();
        for (Map.Entry<Integer, List<Integer>> entry : entries) {
            List<Integer> indices = entry.getValue();
            int size = indices.size();
            for (int i = 2; i < size; i++) {
                int distance = (indices.get(i) - indices.get(i - 2)) * 2;
                minDistance = Math.min(minDistance, distance);
            }
        }
        return minDistance != Integer.MAX_VALUE ? minDistance : -1;
    }
}

###C#

public class Solution {
    public int MinimumDistance(int[] nums) {
        int minDistance = int.MaxValue;
        IDictionary<int, IList<int>> numToIndices = new Dictionary<int, IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n; i++) {
            numToIndices.TryAdd(nums[i], new List<int>());
            numToIndices[nums[i]].Add(i);
        }
        foreach (KeyValuePair<int, IList<int>> pair in numToIndices) {
            IList<int> indices = pair.Value;
            int size = indices.Count;
            for (int i = 2; i < size; i++) {
                int distance = (indices[i] - indices[i - 2]) * 2;
                minDistance = Math.Min(minDistance, distance);
            }
        }
        return minDistance != int.MaxValue ? minDistance : -1;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。需要遍历数组将每个元素的下标列表存入哈希表，然后需要遍历哈希表计算有效三元组的最小距离，每次遍历的时间都是 $O(n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。哈希表的空间是 $O(n)$。

解法

思路和算法

矩阵 $\textit{grid}$ 的大小是 $m \times n$。用 $\textit{total}$ 表示矩阵 $\textit{grid}$ 的所有元素之和。

如果不移除单元格，则判断方法与「3546. 等和矩阵分割 I」相同。

对于移除一个单元格的情况，需要计算两部分的元素和之差 $\textit{diff}$，然后考虑如下两个方面。

1. 判断元素较大的一部分是否包含等于 $\textit{diff}$ 的元素。

2. 判断是否可以从元素较大的一部分移除一个元素 $\textit{diff}$，使得该部分的剩余元素保持连通。

以下说明判断是否存在符合要求的按行分割，判断过程中需要依次遍历矩阵 $\textit{grid}$ 的每一行。

首先考虑只满足最多移除一个单元格的限制，不考虑连通性限制。

使用两个哈希表分别记录矩阵 $\textit{grid}$ 的上边部分和下边部分的每个元素的出现次数，将两个哈希表分别记为 $\textit{partOne}$ 和 $\textit{partTwo}$。初始时，计算矩阵 $\textit{grid}$ 中的所有元素的出现次数并存入哈希表 $\textit{partTwo}$。

从上到下遍历矩阵 $\textit{grid}$ 的每一行，将遍历到的每个元素在哈希表 $\textit{partOne}$ 中将出现次数增加 $1$ 并在哈希表 $\textit{partTwo}$ 中将出现次数减少 $1$，将哈希表 $\textit{partTwo}$ 中的出现次数变成 $0$ 的元素移除，遍历过程中维护遍历到的所有元素之和 $\textit{partOneSum}$，即上边部分的元素之和。每一行遍历结束之后，执行如下操作。

• 如果 $\textit{partOneSum} \times 2 = \textit{total}$，则将当前行作为上边部分的最后一行，即可满足在不移除元素的情况下将矩阵水平分割成元素和相等的两个非空部分。

• 如果 $\textit{partOneSum} \times 2 > \textit{total}$，记 $\textit{diff} = \textit{partOneSum} \times 2 - \textit{total}$，则当哈希表 $\textit{partOne}$ 中存在元素 $\textit{diff}$ 时，将当前行作为上边部分的最后一行，即可满足在从上边部分移除一个元素的情况下将矩阵水平分割成元素和相等的两个非空部分。

• 如果 $\textit{partOneSum} \times 2 < \textit{total}$，记 $\textit{diff} = \textit{total} - \textit{partOneSum} \times 2$，则当哈希表 $\textit{partTwo}$ 中存在元素 $\textit{diff}$ 时，将当前行作为上边部分的最后一行，即可满足在从下边部分移除一个元素的情况下将矩阵水平分割成元素和相等的两个非空部分。

然后考虑连通性限制。如果从一部分移除一个单元格之后导致该部分的剩余元素不连通，则有如下两种情况。

• 该部分的行数等于 $1$ 且列数大于 $1$，移除的单元格的列下标大于 $0$ 且小于 $n - 1$。

• 该部分的行数大于 $1$ 且列数等于 $1$，移除的单元格不是该部分的首行或末行。

为了实现连通性限制，需要做如下调整。

1. 当遍历到行下标 $i = 0$ 时，只将 $\textit{grid}[0][0]$ 和 $\textit{grid}[0][n - 1]$ 在哈希表 $\textit{partOne}$ 中的出现次数增加 $1$，列下标范围 $[1, n - 2]$ 的元素都不更新哈希表 $\textit{partOne}$。行下标 $i = 0$ 的判断结束之后，将列下标范围 $[1, n - 2]$ 的所有元素在哈希表 $\textit{partOne}$ 中的出现次数增加 $1$。

2. 当遍历到行下标 $i = m - 2$ 时，将行下标 $m - 1$ 的列下标范围 $[1, n - 2]$ 的所有元素在哈希表 $\textit{partTwo}$ 中的出现次数减少 $1$，并移除出现次数变成 $0$ 的元素。

3. 当 $n = 1$ 时，对于遍历到的每个行下标 $i$，应做额外判断。如果需要从上边部分移除一个元素 $\textit{diff}$，则必须满足 $\textit{diff} = \textit{grid}[0][0]$ 或 $\textit{diff} = \textit{grid}[i][0]$；如果需要从下边部分移除一个元素 $\textit{diff}$，则必须满足 $\textit{diff} = \textit{grid}[i + 1][0]$ 或 $\textit{diff} = \textit{grid}[m - 1][0]$。

根据上述操作，即可判断是否存在符合要求的按行分割。

使用同样的方法可以判断是否存在符合要求的按列分割，判断过程中需要依次遍历矩阵 $\textit{grid}$ 的每一列。

代码

###Java

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        long total = 0;
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                total += grid[i][j];
            }
        }
        return canPartition(grid, m, n, total, true) || canPartition(grid, m, n, total, false);
    }

    public boolean canPartition(int[][] grid, int m, int n, long total, boolean horizontal) {
        Map<Long, Integer> partOne = new HashMap<Long, Integer>();
        Map<Long, Integer> partTwo = getCounts(grid, m, n, horizontal);
        long partOneSum = 0;
        if (horizontal) {
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n; j++) {
                    partOneSum += grid[i][j];
                    update(grid[i][j], i, j, m, n, horizontal, partOne, partTwo);
                }
                if (i == m - 2) {
                    for (int j = 1; j < n - 1; j++) {
                        long num = grid[m - 1][j];
                        partTwo.put(num, partTwo.get(num) - 1);
                        if (partTwo.get(num) == 0) {
                            partTwo.remove(num);
                        }
                    }
                }
                if (existsPartition(partOneSum, total, partOne, partTwo, n, grid, new int[]{0, 0}, new int[]{i, 0}, new int[]{i + 1, 0}, new int[]{m - 1, 0})) {
                    return true;
                }
                if (i == 0) {
                    for (int j = 1; j < n - 1; j++) {
                        long num = grid[0][j];
                        partOne.put(num, partOne.getOrDefault(num, 0) + 1);
                    }
                }
            }
        } else {
            for (int j = 0; j < n - 1; j++) {
                for (int i = 0; i < m; i++) {
                    partOneSum += grid[i][j];
                    update(grid[i][j], i, j, m, n, horizontal, partOne, partTwo);
                }
                if (j == n - 2) {
                    for (int i = 1; i < m - 1; i++) {
                        long num = grid[i][n - 1];
                        partTwo.put(num, partTwo.get(num) - 1);
                        if (partTwo.get(num) == 0) {
                            partTwo.remove(num);
                        }
                    }
                }
                if (existsPartition(partOneSum, total, partOne, partTwo, m, grid, new int[]{0, 0}, new int[]{0, j}, new int[]{0, j + 1}, new int[]{0, n - 1})) {
                    return true;
                }
                if (j == 0) {
                    for (int i = 1; i < m - 1; i++) {
                        long num = grid[i][0];
                        partOne.put(num, partOne.getOrDefault(num, 0) + 1);
                    }
                }
            }
        }
        return false;
    }

    public Map<Long, Integer> getCounts(int[][] grid, int m, int n, boolean horizontal) {
        Map<Long, Integer> counts = new HashMap<Long, Integer>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                long num = grid[i][j];
                counts.put(num, counts.getOrDefault(num, 0) + 1);
            }
        }
        return counts;
    }

    public void update(long num, int row, int col, int m, int n, boolean horizontal, Map<Long, Integer> partOne, Map<Long, Integer> partTwo) {
        if (remainConnected(row, col, m, n, horizontal)) {
            partOne.put(num, partOne.getOrDefault(num, 0) + 1);
            partTwo.put(num, partTwo.get(num) - 1);
            if (partTwo.get(num) == 0) {
                partTwo.remove(num);
            }
        }
    }

    public boolean existsPartition(long partOneSum, long total, Map<Long, Integer> partOne, Map<Long, Integer> partTwo, int length, int[][] grid, int[] pos0, int[] pos1, int[] pos2, int[] pos3) {
        if (partOneSum * 2 == total) {
            return true;
        } else if (partOneSum * 2 > total) {
            long diff = partOneSum * 2 - total;
            if (partOne.containsKey(diff)) {
                if (length > 1 || (grid[pos0[0]][pos0[1]] == diff || grid[pos1[0]][pos1[1]] == diff)) {
                    return true;
                }
            }
        } else {
            long diff = total - partOneSum * 2;
            if (partTwo.containsKey(diff)) {
                if (length > 1 || (grid[pos2[0]][pos2[1]] == diff || grid[pos3[0]][pos3[1]] == diff)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean remainConnected(int row, int col, int m, int n, boolean horizontal) {
        if (horizontal) {
            return row > 0 || (col == 0 || col == n - 1);
        } else {
            return col > 0 || (row == 0 || row == m - 1);
        }
    }
}

###C#

public class Solution {
    public bool CanPartitionGrid(int[][] grid) {
        long total = 0;
        int m = grid.Length, n = grid[0].Length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                total += grid[i][j];
            }
        }
        return CanPartition(grid, m, n, total, true) || CanPartition(grid, m, n, total, false);
    }

    public bool CanPartition(int[][] grid, int m, int n, long total, bool horizontal) {
        IDictionary<long, int> partOne = new Dictionary<long, int>();
        IDictionary<long, int> partTwo = GetCounts(grid, m, n, horizontal);
        long partOneSum = 0;
        if (horizontal) {
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n; j++) {
                    partOneSum += grid[i][j];
                    Update(grid[i][j], i, j, m, n, horizontal, partOne, partTwo);
                }
                if (i == m - 2) {
                    for (int j = 1; j < n - 1; j++) {
                        long num = grid[m - 1][j];
                        partTwo[num]--;
                        if (partTwo[num] == 0) {
                            partTwo.Remove(num);
                        }
                    }
                }
                if (ExistsPartition(partOneSum, total, partOne, partTwo, n, grid, new int[]{0, 0}, new int[]{i, 0}, new int[]{i + 1, 0}, new int[]{m - 1, 0})) {
                    return true;
                }
                if (i == 0) {
                    for (int j = 1; j < n - 1; j++) {
                        long num = grid[0][j];
                        partOne.TryAdd(num, 0);
                        partOne[num]++;
                    }
                }
            }
        } else {
            for (int j = 0; j < n - 1; j++) {
                for (int i = 0; i < m; i++) {
                    partOneSum += grid[i][j];
                    Update(grid[i][j], i, j, m, n, horizontal, partOne, partTwo);
                }
                if (j == n - 2) {
                    for (int i = 1; i < m - 1; i++) {
                        long num = grid[i][n - 1];
                        partTwo[num]--;
                        if (partTwo[num] == 0) {
                            partTwo.Remove(num);
                        }
                    }
                }
                if (ExistsPartition(partOneSum, total, partOne, partTwo, m, grid, new int[]{0, 0}, new int[]{0, j}, new int[]{0, j + 1}, new int[]{0, n - 1})) {
                    return true;
                }
                if (j == 0) {
                    for (int i = 1; i < m - 1; i++) {
                        long num = grid[i][0];
                        partOne.TryAdd(num, 0);
                        partOne[num]++;
                    }
                }
            }
        }
        return false;
    }

    public IDictionary<long, int> GetCounts(int[][] grid, int m, int n, bool horizontal) {
        IDictionary<long, int> counts = new Dictionary<long, int>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                long num = grid[i][j];
                if (RemainConnected(i, j, m, n, horizontal)) {
                    counts.TryAdd(num, 0);
                    counts[num]++;
                }
            }
        }
        return counts;
    }

    public void Update(long num, int row, int col, int m, int n, bool horizontal, IDictionary<long, int> partOne, IDictionary<long, int> partTwo) {
        if (RemainConnected(row, col, m, n, horizontal)) {
            partOne.TryAdd(num, 0);
            partOne[num]++;
            partTwo[num]--;
            if (partTwo[num] == 0) {
                partTwo.Remove(num);
            }
        }
    }

    public bool ExistsPartition(long partOneSum, long total, IDictionary<long, int> partOne, IDictionary<long, int> partTwo, int length, int[][] grid, int[] pos0, int[] pos1, int[] pos2, int[] pos3) {
        if (partOneSum * 2 == total) {
            return true;
        } else if (partOneSum * 2 > total) {
            long diff = partOneSum * 2 - total;
            if (partOne.ContainsKey(diff)) {
                if (length > 1 || (grid[pos0[0]][pos0[1]] == diff || grid[pos1[0]][pos1[1]] == diff)) {
                    return true;
                }
            }
        } else {
            long diff = total - partOneSum * 2;
            if (partTwo.ContainsKey(diff)) {
                if (length > 1 || (grid[pos2[0]][pos2[1]] == diff || grid[pos3[0]][pos3[1]] == diff)) {
                    return true;
                }
            }
        }
        return false;
    }

    public bool RemainConnected(int row, int col, int m, int n, bool horizontal) {
        if (horizontal) {
            return row > 0 || (col == 0 || col == n - 1);
        } else {
            return col > 0 || (row == 0 || row == m - 1);
        }
    }
}

复杂度分析

• 时间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是矩阵 $\textit{grid}$ 的行数和列数。需要遍历矩阵常数次。

• 空间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是矩阵 $\textit{grid}$ 的行数和列数。哈希表的空间是 $O(mn)$。

解法

思路和算法

矩阵 $\textit{grid}$ 的大小是 $m \times n$，需要计算每个 $k \times k$ 的子矩阵中的任意两个不同值之间的最小绝对差。为了得到最小绝对差，需要得到 $k \times k$ 的子矩阵中的所有元素值，由于最小绝对差一定出现在排序后的两个相邻的不同元素值的差值中，因此需要将子矩阵中的元素值排序，然后计算最小绝对差。

创建 $(m - k + 1) \times (n - k + 1)$ 的二维数组 $\textit{ans}$，计算 $\textit{ans}[i][j]$ 的方法如下。

1. 遍历矩阵 $\textit{grid}$ 的行下标范围 $[i, i + k - 1]$ 和列下标范围 $[j, j + k - 1]$ 中的 $k^2$ 个元素，使用长度为 $k^2$ 的数组存储。

2. 将长度为 $k^2$ 的数组按升序排序，排序之后遍历数组中的每一对相邻元素，如果相邻元素不相等则计算绝对差。遍历结束之后即可得到当前子矩阵中的不同值之间的最小绝对差，填入 $\textit{ans}[i][j]$。

分别计算所有 $k \times k$ 的子矩阵的不同值之间的最小绝对差之后，二维数组 $\textit{ans}$ 即为答案。

代码

###Java

class Solution {
    public int[][] minAbsDiff(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[][] ans = new int[m - k + 1][n - k + 1];
        for (int i = 0; i < m - k + 1; i++) {
            for (int j = 0; j < n - k + 1; j++) {
                ans[i][j] = getMinAbsDiff(grid, k, i, j);
            }
        }
        return ans;
    }

    public int getMinAbsDiff(int[][] grid, int k, int startRow, int startCol) {
        int total = k * k;
        int[] values = new int[total];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                values[i * k + j] = grid[startRow + i][startCol + j];
            }
        }
        Arrays.sort(values);
        int minAbsDiff = Integer.MAX_VALUE;
        for (int i = 1; i < total; i++) {
            if (values[i] > values[i - 1]) {
                minAbsDiff = Math.min(minAbsDiff, values[i] - values[i - 1]);
            }
        }
        return minAbsDiff != Integer.MAX_VALUE ? minAbsDiff : 0;
    }
}

###C#

public class Solution {
    public int[][] MinAbsDiff(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        int[][] ans = new int[m - k + 1][];
        for (int i = 0; i < m - k + 1; i++) {
            ans[i] = new int[n - k + 1];
            for (int j = 0; j < n - k + 1; j++) {
                ans[i][j] = GetMinAbsDiff(grid, k, i, j);
            }
        }
        return ans;
    }

    public int GetMinAbsDiff(int[][] grid, int k, int startRow, int startCol) {
        int total = k * k;
        int[] values = new int[total];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                values[i * k + j] = grid[startRow + i][startCol + j];
            }
        }
        Array.Sort(values);
        int minAbsDiff = int.MaxValue;
        for (int i = 1; i < total; i++) {
            if (values[i] > values[i - 1]) {
                minAbsDiff = Math.Min(minAbsDiff, values[i] - values[i - 1]);
            }
        }
        return minAbsDiff != int.MaxValue ? minAbsDiff : 0;
    }
}

复杂度分析

• 时间复杂度：$O(mnk^2 \log k)$，其中 $m$ 和 $n$ 分别是矩阵 $\textit{grid}$ 的行数和列数，$k$ 是给定的子矩阵边长。需要计算的子矩阵个数是 $O(mn)$，对于每个子矩阵遍历 $k^2$ 个元素存入数组的时间是 $O(k^2)$，将数组排序的时间是 $O(k^2 \log k^2) = O(k^2 \log k)$，因此每个子矩阵的计算时间是 $O(k^2 \log k)$，时间复杂度是 $O(mnk^2 \log k)$。

• 空间复杂度：$O(k^2)$，其中 $k$ 是给定的子矩阵边长。对于每个子矩阵计算差值时需要创建长度为 $k^2$ 的数组，将数组排序的空间是 $O(\log k^2) = O(\log k)$，因此空间复杂度是 $O(k^2)$。

解法

思路和算法

用 $n$ 表示字符串 $s$ 的长度。由于 $n \le 1000$，因此可以枚举字符串 $s$ 的所有子串并判断是否为平衡子串。对于 $0 \le i < n$ 的每个下标 $i$，从小到大遍历 $i \le j < n$ 的所有下标 $j$，对于每个下标 $j$ 判断下标范围 $[i, j]$ 的子串是否为平衡子串。

具体做法是，对于每个起始下标 $i$，使用哈希表记录子串中的每个字符的出现次数。当起始下标 $i$ 确定时，对于遍历到的每个下标 $j$，执行如下操作。

1. 在哈希表中将字符 $s[j]$ 的出现次数增加 $1$。

2. 遍历哈希表中的所有记录，判断是否满足哈希表中的每个字符的出现次数都与字符 $s[j]$ 的出现次数相等。如果出现次数都相等，则下标范围 $[i, j]$ 的子串是平衡子串，其长度是 $j - i + 1$，使用该平衡子串的长度更新最长平衡子串的长度。

遍历结束之后，即可得到字符串 $s$ 的最长平衡子串的长度。

代码

###Java

class Solution {
    public int longestBalanced(String s) {
        int longest = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            Map<Character, Integer> counts = new HashMap<Character, Integer>();
            Set<Map.Entry<Character, Integer>> entries = counts.entrySet();
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                int count = counts.getOrDefault(c, 0) + 1;
                counts.put(c, count);
                boolean isBalanced = true;
                for (Map.Entry<Character, Integer> entry : entries) {
                    if (entry.getValue() != count) {
                        isBalanced = false;
                        break;
                    }
                }
                if (isBalanced) {
                    longest = Math.max(longest, j - i + 1);
                }
            }
        }
        return longest;
    }
}

###C#

public class Solution {
    public int LongestBalanced(string s) {
        int longest = 0;
        int n = s.Length;
        for (int i = 0; i < n; i++) {
            IDictionary<char, int> counts = new Dictionary<char, int>();
            for (int j = i; j < n; j++) {
                char c = s[j];
                counts.TryAdd(c, 0);
                counts[c]++;
                bool isBalanced = true;
                foreach (KeyValuePair<char, int> pair in counts) {
                    if (pair.Value != counts[c]) {
                        isBalanced = false;
                        break;
                    }
                }
                if (isBalanced) {
                    longest = Math.Max(longest, j - i + 1);
                }
            }
        }
        return longest;
    }
}

复杂度分析

• 时间复杂度：$O(n^2 |\Sigma|)$，其中 $n$ 是字符串 $s$ 的长度，$\Sigma$ 是字符集，这道题中 $\Sigma$ 是全部小写英语字母，$|\Sigma| = 26$。需要遍历的子串数量是 $O(n^2)$，对于每个子串遍历哈希表判断是否为平衡子串的时间是 $O(|\Sigma|)$，因此时间复杂度是 $O(n^2 |\Sigma|)$。

• 空间复杂度：$O(\min(n, |\Sigma|))$，其中 $n$ 是字符串 $s$ 的长度，$\Sigma$ 是字符集，这道题中 $\Sigma$ 是全部小写英语字母，$|\Sigma| = 26$。哈希表的空间是 $O(\min(n, |\Sigma|))$。