โจทย์
นับจำนวนคู่ของตำแหน่งที่แตกต่างกัน i < j ใน numbers ที่ numbers[i] + numbers[j] เท่ากับ target โดยใช้ลูปซ้อนสองชั้น
เขียนฟังก์ชัน count_pairs_with_sum(numbers, target)
อินพุต
numbers: ลิสต์ของจำนวนเต็ม target: ผลรวมที่ต้องการหา
เอาต์พุต
คืนค่าจำนวนคู่ที่พบ
เงื่อนไข
0 ≤ ความยาวของ numbers ≤ 500; -10,000 ≤ แต่ละจำนวน, target ≤ 10,000
ตัวอย่าง
อินพุต:
target = 6
numbers = [1, 5, 3, 3, 4]
ผลลัพธ์ที่คาดหวัง:
expected = 2
อินพุต:
long long target = 6;
std::vector<long long> numbers = {1, 5, 3, 3, 4};
ผลลัพธ์ที่คาดหวัง:
long long expected = 2;
อินพุต:
long target = 6;
long[] numbers = new long[] {1, 5, 3, 3, 4};
ผลลัพธ์ที่คาดหวัง:
long expected = 2;
คำอธิบาย
1 + 5, 3 + 3 (เลข 3 สองตัวที่ตำแหน่งต่างกัน) รวมกันได้ 6: มี 2 คู่
อินพุต:
target = 4
numbers = [2, 2, 2]
ผลลัพธ์ที่คาดหวัง:
expected = 3
อินพุต:
long long target = 4;
std::vector<long long> numbers = {2, 2, 2};
ผลลัพธ์ที่คาดหวัง:
long long expected = 3;
อินพุต:
long target = 4;
long[] numbers = new long[] {2, 2, 2};
ผลลัพธ์ที่คาดหวัง:
long expected = 3;
คำอธิบาย
ทุกคู่ของเลข 2 ทั้งสามตัวรวมกันได้ 4: ตำแหน่ง (0,1), (0,2), (1,2) = 3 คู่
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ตรวจทุกคู่ที่อยู่ก่อน-หลังกัน แล้วดูว่าผลบวกตรงกับค่าเป้าหมายไหม
คำใบ้ 2
ใช้ลูปซ้อนสองชั้นแบบตรงไปตรงมาก็พอ เพราะขนาดอินพุตเล็ก
คำใบ้ 3
ระวังให้นับแต่ละคู่เพียงครั้งเดียว โดยใช้ตำแหน่งที่ i น้อยกว่า j
ความซับซ้อนที่คาดหวัง
เวลา O(n^2), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน