解法

思路和算法

矩阵 $\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|))$。

解法

思路和算法

根据题意模拟，计算结果数组 $\textit{result}$ 即可。

用 $n$ 表示数组 $\textit{nums}$ 的长度。对于 $0 \le i < n$ 的每个下标 $i$，计算 $\textit{result}[i]$ 的方法如下。

• 当 $\textit{nums}[i] > 0$ 时，$\textit{result}[i]$ 的值等于数组 $\textit{nums}$ 的下标 $i$ 向右移动 $\textit{nums}[i]$ 的下标处的值，即数组 $\textit{nums}[i]$ 的下标 $i + \textit{nums}[i]$ 对应的范围 $[0, n - 1]$ 中的下标。

• 当 $\textit{nums}[i] < 0$ 时，$\textit{result}[i]$ 的值等于数组 $\textit{nums}$ 的下标 $i$ 向左移动 $-\textit{nums}[i]$ 的下标处的值，即数组 $\textit{nums}[i]$ 的下标 $i + \textit{nums}[i]$ 对应的范围 $[0, n - 1]$ 中的下标。

• 当 $\textit{nums}[i] = 0$ 时，$\textit{result}[i]$ 的值等于数组 $\textit{nums}$ 的下标 $i$ 处的值。

上述情况可以统一表示成数组 $\textit{nums}[i]$ 的下标 $i + \textit{nums}[i]$ 对应的范围 $[0, n - 1]$ 中的下标。对于 $0 \le i < n$ 的每个下标 $i$，计算 $\textit{result}[i]$ 时为了确保得到范围 $[0, n - 1]$ 中的下标，应计算 $\textit{index} = ((i + \textit{nums}[i]) \bmod n + n) \bmod n$，则 $\textit{result}[i] = \textit{nums}[\textit{index}]$。

计算数组 $\textit{result}$ 中的所有元素之后，即可得到结果数组。

代码

###Java

class Solution {
    public int[] constructTransformedArray(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int index = ((i + nums[i]) % n + n) % n;
            result[i] = nums[index];
        }
        return result;
    }
}

###C#

public class Solution {
    public int[] ConstructTransformedArray(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int index = ((i + nums[i]) % n + n) % n;
            result[i] = nums[index];
        }
        return result;
    }
}

###C++

class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            int index = ((i + nums[i]) % n + n) % n;
            result[i] = nums[index];
        }
        return result;
    }
};

###Python

class Solution:
    def constructTransformedArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        return [nums[(i + nums[i]) % n] for i in range(n)]

###C

int* constructTransformedArray(int* nums, int numsSize, int* returnSize) {
    int* result = (int*) malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        int index = ((i + nums[i]) % numsSize + numsSize) % numsSize;
        result[i] = nums[index];
    }
    *returnSize = numsSize;
    return result;
}

###Go

func constructTransformedArray(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := 0; i < n; i++ {
        index := ((i + nums[i]) % n + n) % n
        result[i] = nums[index]
    }
    return result
}

###JavaScript

var constructTransformedArray = function(nums) {
    let n = nums.length;
    let result = new Array(n);
    for (let i = 0; i < n; i++) {
        let index = ((i + nums[i]) % n + n) % n;
        result[i] = nums[index];
    }
    return result;
};

###TypeScript

function constructTransformedArray(nums: number[]): number[] {
    let n = nums.length;
    let result = new Array(n);
    for (let i = 0; i < n; i++) {
        let index = ((i + nums[i]) % n + n) % n;
        result[i] = nums[index];
    }
    return result;
};

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。结果数组的每个元素的计算时间都是 $O(1)$。

• 空间复杂度：$O(1)$。注意返回值不计入空间复杂度。