【LeetCode 1991 找到数组的中间位置 / LeetCode 724 寻找数组的中心下标】中间索引问题

1991 题目描述

暴力解法1：

思路：

1. 遍历下标，求出左边和和右边和
2. 比较两边是否相等
3. 相等直接返回值
4. 没有符合的返回 -1

	class Solution {public int findMiddleIndex(int[] nums) {int len=nums.length;//初始化一个变量 midIndex 为 -1，用于存储中间索引的结果。如果找不到中间索引，则返回 -1。int midIndex=-1;for(int i=0;i<len;i++){/**对于数组中的每个索引 i：初始化两个变量 leftSum 和 rightSum 为 0，分别用于存储当前索引左侧和右侧元素的和。计算左侧元素之和 leftSum: 使用一个从 i 到 0 的倒序循环来累加左侧元素的值。每次循环迭代中，将 nums[j] 加到 leftSum 上。计算右侧元素之和 rightSum:使用一个从 i 到数组末尾的正序循环来累加右侧元素的值。每次循环迭代中，将 nums[k] 加到 rightSum 上。如果 leftSum 等于 rightSum，则找到了中间索引，返回当前索引 i 并设置 midIndex 为 i。*/int leftSum=0,rightSum=0;for(int j=i;j>=0;j--)leftSum+=nums[j];for(int k=i;k<len;k++)rightSum+=nums[k];if(leftSum==rightSum)return midIndex=i;}return midIndex;}}

时间复杂度
这段代码的时间复杂度为 O(n^2)，其中 n 是数组 nums 的长度。这是因为在最坏的情况下，需要对每个索引 i 都重新计算左侧和右侧元素的和，每个计算的时间复杂度为 O(n)。
空间复杂度:
该方法的空间复杂度为常数：复杂度为O(1)，因为它使用的额外空间不随输入数组的大小变化。所有的变量都占用固定的空间，无论数组有多长，这些变量占用的空间大小都是相同的。

暴力解法2：

思路：
根据题目描述可以总结以下规律：

1. SUM（midIndx左边所有元素的值）等于SUM（midIndx右边所有元素的值）
2. SUM（所有元素的值） = SUM（midIndx左边所有元素的值）+SUM（midIndx右边所有元素的值）+ midIndex的值
3. midIndex的值 = SUM（所有元素的值）-（SUM（midIndx左边所有元素的值）+SUM（midIndx右边所有元素的值））
4. midIndex的值 = SUM（所有元素的值）- 2*SUM（midIndx左边所有元素的值）或者
5. midIndex的值 = SUM（所有元素的值）- 2*SUM（midIndx右边所有元素的值）

具体到代码中如下：

class Solution {public int findMiddleIndex(int[] nums) {int sum = Arrays.stream(nums).sum();int left = 0;int len = nums.length;if(len==1){return 0;}for (int i = 0; i < nums.length; ++i) {if (2*left +nums[i]== sum) {return i;}left +=nums[i];}return -1;}
}

本题对应链接：https://leetcode.cn/problems/find-the-middle-index-in-array/description/

724 题目描述 ：

暴力解法3：

思路：
根据题目描述可以总结以下规律：

1. SUM（midIndx左边所有元素的值）等于SUM（midIndx右边所有元素的值）
2. 如果 SUM（所有元素的值）-midIndex的值 = SUM（midIndx左边所有元素的值）则midIndex找到了
3. 如果 SUM（所有元素的值）-midIndex的值 > SUM（midIndx左边所有元素的值）,则需要继续推进midIndex的下标

具体代码如下：

class Solution {public int findMiddleIndex(int[] nums) {int sum = Arrays.stream(nums).sum();int left = 0;int right = sum;for (int i = 0; i < nums.length; i++) {right -= nums[i];if (left == right) {return i;}left +=nums[i];}return -1;}
}

本题对应链接：https://leetcode.cn/problems/find-pivot-index/description/