โจทย์
Count the pairs of different positions i < j in numbers where numbers[i] + numbers[j] equals target. Use two nested loops.
Implement count_pairs_with_sum(numbers, target).
Input
numbers: The list of integers. target: The sum to look for.
Output
Return the number of pairs.
เงื่อนไข
0 ≤ length of numbers ≤ 500; -10,000 ≤ each number, 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 (the two 3s at different positions) make 6: 2 pairs.
อินพุต:
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;คำอธิบาย
Every pair of the three 2s sums to 4: positions (0,1), (0,2), (1,2) = 3 pairs.
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
Check every earlier-later pair and see whether their sum matches the target.
คำใบ้ 2
A straightforward double loop is enough because the input size is small.
คำใบ้ 3
Be careful to count each pair once, using positions with i less than j.
ความซับซ้อนที่คาดหวัง
O(n^2) time, O(1) extra space
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน