kalan unsurların toplamına eşittir dizideki öğeye bulun

Question

aşağıdaki sorunu çözer verimli bir algoritma düşünmeye çalışıyorum:

tamsayılar dizisi göz önüne alındığında, öğenin dizinini döndürür dizideki kalan elemanların toplamına eşit olan dizi; Eğer böyle bir eleman yoksa, -1'e geri dönün.

Örneğin, [1,2,3,6] dizisi verilir, sonra, 4 6=1+2+3; yana [3, -3, 5, 1] verilen geri 3 = -3 + 5 + 1 yana 0 döndürür.

Herhangi bir düşünce?

Answer 1

iki çalışır bu çözün:

• birinci vadede ikinci vadede dizinin
• tüm sayının toplamını oluşturmak, her bir elemanın i kontrol, arrSum == i * 2 geçerli olup olmadığı - eşdeğer arrSum - i == i için . Eğer tutarsa, aranan öğenizi buldunuz. kodunda

: O(n) yılında

int sum = 0; 
for(int i : arr) 
    sum += i; 

for(int i = 0 ; i < arr.length ; i++) 
    if(sum == arr[i] * 2) 
     return i; 

return -1; 

çalıştırır.