1991. 找到数组的中间位置

Problem: 1991. 找到数组的中间位置

解题思路

首先无脑暴力看看能不能过，再看怎么优化

类型	复杂度
时间复杂度	$O(n^2)$
空间复杂度	$O(1)$

C++

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        for (auto i = 0; i < nums.size(); i++){
            auto l = 0, r = 0;
            for (auto li = 0; li < i; li++){
                l += nums.at(li);
            }
            for (auto ri = i + 1; ri < nums.size(); ri++){
                r += nums.at(ri);
            }
            if (l == r) return i;
        }
        return -1;
    }
};

C

int findMiddleIndex(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++){
        int l = 0, r = 0;
        for (int li = 0; li < i; li++){
            l += nums[li];
        }
        for (int ri = i + 1; ri < numsSize; ri++){
            r += nums[ri];
        }
        if (l == r) return i;
    }
    return -1;
}

C#

public class Solution {
    public int FindMiddleIndex(int[] nums) {
        for (var i = 0; i < nums.Length; i++){
            int l = 0, r = 0;
            for (var li = 0; li < i; li++){
                l += nums[li];
            }
            for (var ri = i + 1; ri < nums.Length; ri++){
                r += nums[ri];
            }
            if (l == r) return i;
        }
        return -1;
    }
}

Go

func findMiddleIndex(nums []int) int {
    for i := 0; i < len(nums); i++ {
        var l, r = 0, 0;
        for li := 0; li < i; li++{
            l += nums[li];
        }
        for ri := i + 1; ri < len(nums); ri++ {
            r += nums[ri];
        }
        if (l == r) {
            return i;
        }
    }
    return -1;
}

Python

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            li = ri = 0
            li = sum(nums[:i])
            ri = sum(nums[(i+1):])
            if li == ri: return i
        return -1

然后不难发现，每次循环左和都是上一次循环加上 nums[i] ，而右和则是减去 nums[i] ，根据这个规律，就可以把内部的循环简化掉

类型	复杂度
时间复杂度	$O(n)$
空间复杂度	$O(1)$

C++

class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        auto ls = 0, rs = 0;
        for (auto i = 0; i < nums.size(); i++){
            rs += nums.at(i);
        }
        for (auto i = 0; i < nums.size(); i++){
            rs -= nums.at(i);
            if (ls == rs) return i;
            ls += nums.at(i);
        }
        return -1;
    }
};

C

int findMiddleIndex(int* nums, int numsSize) {
    int ls = 0, rs = 0;
    for (int i = 0; i < numsSize; i++){
        rs += nums[i];
    }
    for (int i = 0; i < numsSize; i++){
        rs -= nums[i];
        if (ls == rs) return i;
        ls += nums[i];
    }
    return -1;
}

C#

public class Solution {
    public int FindMiddleIndex(int[] nums) {
        int ls = 0, rs = 0;
        for (var i = 0; i < nums.Length; i++){
            rs += nums[i];
        }
        for (var i = 0; i < nums.Length; i++){
            rs -= nums[i];
            if (ls == rs) return i;
            ls += nums[i];
        }
        return -1;
    }
}

Go

func findMiddleIndex(nums []int) int {
    var ls, rs = 0, 0;
    for i := 0; i < len(nums); i++ {
        rs += nums[i]
    }
    for i := 0; i < len(nums); i++ {
        rs -= nums[i];
        if (ls == rs) {
            return i;
        }
        ls += nums[i];
    }
    return -1;
}

Python

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        ls = 0
        rs = sum(nums)
        for i in range(len(nums)):
            rs -= nums[i]
            if ls == rs: return i
            ls += nums[i]
        return -1