สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums ตอนนี้ให้พิจารณาฟังก์ชันว่า f(i) ซึ่งลบองค์ประกอบที่ดัชนี i แล้วคืนค่าจริงหรือเท็จ ทั้งนี้ขึ้นอยู่กับผลรวมของค่าดัชนีคู่ในรายการผลลัพธ์จะเหมือนกับผลรวมของค่าดัชนีคี่หรือไม่ ดังนั้นเราจึงต้องการจำนวนดัชนีที่ f จะคืนค่าเป็นจริง
ดังนั้น ถ้าอินพุตเป็น nums =[6, 8, 5, 2, 3] ผลลัพธ์จะเป็น 2 เพราะถ้าเราลบ 8 อาร์เรย์จะเป็น [6, 5, 2, 3] คี่ และแม้แต่ผลรวมขององค์ประกอบดัชนีคือ 8 ดังนั้นจึงเหมือนกัน วิธีแก้ปัญหาที่เป็นไปได้อีกวิธีหนึ่งคือ หากเราลบ 2 อาร์เรย์จะเป็น [6, 8, 5, 3] ในที่นี้ผลรวมขององค์ประกอบที่จัดทำดัชนีและคี่คือ 11 ดังนั้นพวกมันจึงเหมือนกัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของ nums
- a :=รายการ 2d ของคำสั่ง 2 x (n+1) และเติมแต่ละรายการด้วย 0s
- สำหรับแต่ละดัชนี i และค่า x nums ทำ
- a[0, i + 1] :=a[0, i]
- a[1, i + 1] :=a[1, i]
- a[i mod 2, i + 1] :=a[i mod 2, i + 1] + x
- ค :=0
- s :=ผลรวมขององค์ประกอบทั้งหมดที่มีอยู่ใน nums
- สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
- e :=a[0, i] - a[0, 0] + a[1, n] - a[1, i + 1]
- ถ้า e * 2 เหมือนกับ s - nums[i] แล้ว
- c :=c + 1
- คืนค
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(nums): n = len(nums) a = [[0] * (n + 1), [0] * (n + 1)] for i, x in enumerate(nums): a[0][i + 1] = a[0][i] a[1][i + 1] = a[1][i] a[i % 2][i + 1] += x c = 0 s = sum(nums) for i in range(n): e = a[0][i] - a[0][0] + a[1][n] - a[1][i + 1] if e * 2 == s - nums[i]: c += 1 return c nums = [6, 8, 5, 2, 3] print(solve(nums))
อินพุต
[6, 8, 5, 2, 3]
ผลลัพธ์
2
