Giả sử chúng ta có mảng A các số, chúng ta phải tìm tất cả chỉ số của mảng này sao cho sau khi xóa phần tử thứ i, mảng sẽ trở thành "mảng tốt". Lưu ý:
- Mảng tốt là mảng có một phần tử bằng tổng của tất cả các phần tử còn lại.
- Sử dụng chỉ số 1-based (bắt đầu từ 1).
Ví dụ, nếu đầu vào là [10,4,6,2], thì đầu ra là [1,4] vì xóa A[1] -> [4,6,2] tốt vì 6=4+2; xóa A[4] -> [10,4,6] tốt vì 10=4+6.
Giải pháp:
- n = len(A), add = 0, my_map = defaultdict(int)
- Đếm tần suất và tổng add
- Với mỗi i: k = add - A[i]; nếu k chẵn: k //= 2; nếu k trong my_map và (A[i]==k và my_map[k]>1 hoặc A[i]!=k) thì in i+1
Ví dụ
from collections import defaultdict
def find_indices(A):
n = len(A)
add = 0
my_map = defaultdict(lambda:0)
for i in range(n):
my_map[A[i]] += 1
add += A[i]
for i in range(n):
k = add - A[i]
if k % 2 == 0:
k = k >> 1
if k in my_map:
if ((A[i] == k and my_map[k] > 1) or (A[i] != k)):
print((i + 1))
A = [10, 4, 6, 2]
find_indices(A)
Đầu vào
[10, 4, 6, 2]
Đầu ra
1 4