โปรแกรม C++ หาจำนวนคู่ในอาร์เรย์ที่ตรงตามเงื่อนไข

กำหนดอาร์เรย์ nums ขนาด n ต้องการหาจำนวนคู่ (i, j) ที่ i < j และ j - i = nums[i] + nums[j] (ความต่างตำแหน่งเท่ากับผลรวมค่า) จำนวนคู่ทั้งหมดที่เป็นไปได้คือ n(n-1)/2

ตัวอย่าง: n=8, nums={4,2,1,0,1,2,3,3} ผลลัพธ์: 13

ขั้นตอนการแก้ปัญหา (Two-pointer / Binary Search)

1. สร้างอาร์เรย์ vals[i] = i + 1 - nums[i] (1-based index)
2. เรียงลำดับ vals
3. สำหรับแต่ละ i คำนวณ k = nums[i] + i + 1
4. หาจำนวนค่าใน vals ที่เท่ากับ k โดยใช้ upper_bound - lower_bound บวกเข้า res
5. คืนค่า res

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int solve(int n, vector<int> nums) {
    vector<int> vals(n);
    for (int i = 0; i < n; i++) vals[i] = i + 1 - nums[i];
    sort(vals.begin(), vals.end());
    int res = 0;
    for (int i = 0; i < n; i++) {
        int k = nums[i] + i + 1;
        res += upper_bound(vals.begin(), vals.end(), k) - lower_bound(vals.begin(), vals.end(), k);
    }
    return res;
}

int main() {
    int n = 8;
    vector<int> nums = {4, 2, 1, 0, 1, 2, 3, 3};
    cout << solve(n, nums);
    return 0;
}

อินพุต / เอาต์พุต

Input: 8, {4, 2, 1, 0, 1, 2, 3, 3}

Output: 13