สมมติว่าเราได้รับ n ตัวเลขในอาร์เรย์ nums เราต้องเลือกคู่ตัวเลขสองตัวจากอาร์เรย์ และมีเงื่อนไขว่าผลต่างของตำแหน่งในอาร์เรย์จะเท่ากับผลรวมของตัวเลขทั้งสอง สามารถมีจำนวนคู่ทั้งหมดได้ n(n - 1)/2 จากอาร์เรย์ของตัวเลขที่กำหนด เราต้องหาจำนวนคู่ดังกล่าวทั้งหมดจากอาร์เรย์
ดังนั้น หากอินพุตเป็น n =8, nums ={4, 2, 1, 0, 1, 2, 3, 3} ผลลัพธ์จะเป็น 13
ในอาร์เรย์สามารถมี 13 คู่ดังกล่าวได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
Define an array vals(n) for initialize i := 0, when i < n, update (increase i by 1), do: vals[i] := i + 1 - nums[i] sort the array vals res := 0 for initialize i := 0, when i < n, update (increase i by 1), do: k := nums[i] + i + 1 res := res + (position of first occurrence of a value not less than k in array vals - position of first occurrence of a value not greater than k in array vals) return res
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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;
} อินพุต
8, {4, 2, 1, 0, 1, 2, 3, 3}
ผลลัพธ์
13
