一、思路
1. 先看暴力做法
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(a[i]+b[j]==x)
return i j
=> 复杂度 O(n * m)
2. 双指针优化
双指针算法的优化方向,找单调性。
因为 a[i] + b[j] = x, x 为定值,故,当a[i]单调上升时,b[j]必然单调递减。
for(i = 0, j = m - 1; i < n; i++)
while(j >= 0; a[i]+b[j] > x ) j--;
if(a[i]+b[j] == x) return i j
=> 复杂度 O(n + m)
二、实现
let getCouple = (arr1, arr2, x) => {
for (let i = 0, j = arr2.length - 1; i < arr1.length; i++) {
while (j > 0 && arr1[i] + arr2[j] > x) j --;
if(arr1[i] + arr2[j] === x) return [i,j];
}
}
var buf = '';
process.stdin.on('readable', function () {
var chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputArgs = line => {
return line.split(' ').filter(s => s !== '').map(x => parseInt(x));
}
process.stdin.on('end', function () {
let arr1 =[], arr2=[], x;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let firstline = getInputArgs(line);
x = firstline[2];
}
else if (lineIdx === 1)
arr1 = getInputArgs(line);
else if (lineIdx === 2){
arr2 = getInputArgs(line);
console.log(getCouple(arr1,arr2,x).join(' '));
}
});
});