【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;
	   }
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度
这段代码的时间复杂度为 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

本题对应链接：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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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