每日算法 - 250530

记录一下今天完成的LeetCode算法题目，包含思路、解题过程、复杂度分析和代码实现。

---

3128. 直角三角形

题目

思路

数组

解题过程

显而易见的是，我们枚举中间的顶点最好计算。当我们的中间顶点是1时，它能够组成的直角三角形的个数就是这一行除了它以外的1的个数乘上这一列除了它以外的1的个数。

复杂度

• 时间复杂度: $O(NM)$
• 空间复杂度: $O(N+M)$

Code

class Solution {public long numberOfRightTriangles(int[][] grid) {long ret = 0;int r = grid.length;int c = grid[0].length;int[] r1 = new int[r];int[] c1 = new int[c];for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {if (grid[i][j] == 1) {r1[i]++;c1[j]++;}}}for (int i = 0; i < r; i++) {for (int j = 0; j < c; j++) {if (grid[i][j] == 1) {ret += (long)(r1[i] - 1) * (c1[j] - 1);}}}return ret;}
}

---

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

思路

前缀和

解题过程

我们可以在初始化的时候将nums预处理成一个前缀和数组dp。dp[i]表示[0, i]区间的和。那么sumRange(left, right)方法只需返回 dp[right] - dp[left - 1] 就可以得到 [left, right] 区间的和了。
需要注意的是：当 left=0 时，dp[right] 就是 [0, right] 的和，此时不能减去 dp[left - 1]，可以直接返回 dp[right]。

复杂度

• 时间复杂度: 初始化是 $O(N)$，sumRange 是 $O(1)$
• 空间复杂度: $O(N)$ (如果创建新的dp数组) 或 $O(1)$ (如果在原数组上修改，不计输入数组本身)

Code

class NumArray {private int[] prefixSums;public NumArray(int[] nums) {prefixSums = new int[nums.length];prefixSums[0] = nums[0];for (int i = 1; i < nums.length; i++) {prefixSums[i] = prefixSums[i - 1] + nums[i];}}public int sumRange(int left, int right) {if (prefixSums.length == 0 || left < 0 || right >= prefixSums.length || left > right) {return 0; }if (left == 0) {return prefixSums[right];}return prefixSums[right] - prefixSums[left - 1];}
}/*** Your NumArray object will be instantiated and called as such:* NumArray obj = new NumArray(nums);* int param_1 = obj.sumRange(left,right);*/

---

3427. 变长子数组求和

题目

思路

前缀和

解题过程

1. 首先，预处理得到前缀和数组 dp，其中 dp[i] 表示原数组 nums 中区间 [0, i] 的元素之和。
2. 遍历数组 nums，对于每个索引 i：
   • 题目描述指出，对于索引 i，子数组 nums[start...i] 的长度为 nums[i]。
   • 这意味着 i - start + 1 = nums[i]，所以 start = i - nums[i] + 1。
   • 该子数组 nums[actualStart...i] 的和可以通过前缀和数组计算：dp[i] - (actualStart == 0 ? 0 : dp[actualStart - 1])。
3. 将所有这些子数组的和累加起来即为最终答案。

复杂度

• 时间复杂度: $O(N)$
• 空间复杂度: $O(N)$

Code

class Solution {public int subarraySum(int[] nums) {int sum = 0, n = nums.length;int[] dp = new int[n];dp[0] = nums[0];for (int i = 1; i < n; i++) {dp[i] = dp[i - 1] + nums[i];}for (int i = 0; i < n; i++) {int start = Math.max(0, i - nums[i]);sum += (start == 0) ? dp[i] : dp[i] - dp[start - 1];}return sum;}
}

---

2874. 有序三元组中的最大值 II（复习）

题目

这是第二次写这道题了，已经算是掌握了，就不再多说了，详细题解见每日算法-250527

代码

class Solution {public long maximumTripletValue(int[] nums) {long ret = 0;int n = nums.length;int[] suffixMax = new int[n];suffixMax[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--) {suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);}int privMax = nums[0];for (int i = 1; i < n - 1; i++) {ret = Math.max(ret, ((long) (privMax - nums[i]) * suffixMax[i + 1]));privMax = Math.max(privMax, nums[i]);}return ret;}
}