Find the Middle Index in Array (Easy)

Bài toán

Tiếp theo chuỗi bài về thuật toán, bài thứ 4 tôi xin giới thiệu là bài Find-the-middle-index-in-array

https://leetcode.com/problems/find-the-middle-index-in-array/

Tôi xin tóm tắt lại bài toán như sau:

Cho một mảng số nguyên nums có chỉ số bắt đầu từ 0. Tìm chỉ số middleIndex trái nhất (tức là chỉ số nhỏ nhất trong tất cả các chỉ số thỏa mãn điều kiện sau):

• Một middleIndex là một chỉ số thỏa mãn điều kiện sau: nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1].
• Nếu middleIndex == 0, ta coi tổng bên trái bằng 0. Tương tự, nếu middleIndex == nums.length - 1, ta coi tổng bên phải bằng 0.

Trả về chỉ số middleIndex trái nhất thỏa mãn điều kiện, hoặc -1 nếu không có chỉ số nào thỏa mãn điều kiện đó.

Ví dụ:

Example 1:

Input: nums = [2,3,-1,8,4]
Output: 3
Explanation: The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4

Example 2:

Input: nums = [1,-1,4]
Output: 2
Explanation: The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0

Example 3:

Input: nums = [2,5]
Output: -1
Explanation: There is no valid middleIndex.

Hướng giải quyết

Nhận xét

Giả sử tồn tại vị trí middleIndex dễ dàng thấy được :

Tổng bên trái của nums (từ 0→middleIndex-1) + tổng bên phải của nums (từ middleIndex+1 →n) = Tổng toàn bộ của nums - nums[middleIndex]

⇒ Mình chỉ cần tìm tổng S của dãy nums và tính tổng cộng dồn S1 (tổng nums từ vị trí 0 đến vị trí đang duyệt). Duyệt từ vị trí đầu tiên đến lúc gặp điều kiện thoải mã S1 == S - nums[i] - S1 ⇒ i là vị trí cần tìm. Ngược lại nếu duyệt hết vẫn không tồn tại thì trả ra -1

Giải pháp

• Bước 1: Tính tổng của toàn bộ mảng nums và lưu vào biến s.
• Bước 2: Khởi tạo biến s1 bằng 0.
• Bước 3: Duyệt qua các phần tử của mảng nums bằng vòng lặp for và thực hiện các bước sau:
  • Kiểm tra nếu tổng của các phần tử bên trái phần tử thứ i (tức là tổng các phần tử từ nums[0] đến nums[i-1]) bằng tổng của các phần tử bên phải phần tử thứ i (tức là tổng các phần tử từ nums[i+1] đến nums[len(nums)-1]) và lượng nums[i] đang xét thì trả về chỉ số i.
  • Nếu không tìm thấy phần tử thỏa mãn điều kiện trên, cập nhật giá trị của biến s1 bằng cộng thêm nums[i].

Bước 4: Nếu không tìm thấy phần tử thỏa mãn điều kiện sau khi duyệt qua toàn bộ mảng nums thì trả về -1.

Chạy thử với nums=[2,3,-1,8,4]

• Bước 1: s = 2 + 3 - 1 + 8 + 4 = 16
• Bước 2: s1 = 0
• Bước 3 :
  • i = 0 ,0 = s1 ≠ s - s1 - nums[0] = 16 - 2 = 14 ,s1 = s1 + nums[0] = 0 + 2 = 2
  • i = 1 , 2 = s1 ≠ s - s1 - nums[1] = 16 - 3 - 2 = 11 ,s1 = s1 + nums[1] = 2 + 3 = 5
  • i = 2 , 5 = s1 ≠ s - s1 - nums[2] = 16 - 5 - (-1) = 12 ,s1 = s1 + nums[2] = 5 + (-1) = 4
  • i = 3 , 4 = s1 = s - s1 - nums[3] = 16 - 4 - 8 = 4 ⇒ trả kết quả là 3

Python Code

from typing import List

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

Link nộp bài : https://leetcode.com/problems/find-the-middle-index-in-array/