題目詳情:
輸(shu)入一個(ge)遞增排序的(de)(de)數(shu)組和(he)一個(ge)數(shu)字(zi)s,在數(shu)組中查找(zhao)兩個(ge)數(shu),使(shi)得它們的(de)(de)和(he)正好是s。如果有多對數(shu)字(zi)的(de)(de)和(he)等于s,則輸(shu)出任意一對即(ji)可(ke)。
示例:
輸入:nums = [2,7,11,15], target = 9
輸出:[2,7] 或者(zhe) [7,2]
解題思路:
首先,定(ding)義兩個指針 left 和 right,分別指向(xiang)數組(zu)的最左端和最右端。
然后,我們計算指(zhi)針(zhen)所指(zhi)元素的和 sum。如果(guo) sum 等于 target,則找到了符合條件的一對數字,即 nums[left] 和 nums[right],將它們作為(wei)結果(guo)返回(hui)。
如(ru)果 sum 小于 target,說明(ming)當前的和太小了(le),我們需要增大和,為了(le)達到(dao)這(zhe)個目標,我們將 left 指針(zhen)向右移動一位。
如果 sum 大于 target,說明當前的和太大了(le),我們需要減(jian)小(xiao)和,為了(le)達到這個(ge)目(mu)標(biao),我們將 right 指針(zhen)向(xiang)左(zuo)移(yi)動一(yi)位。
重復上述(shu)步驟,直到找到一對數(shu)字(zi)的和等于(yu) target,或者指針相遇(即(ji) left 大于(yu)等于(yu) right),此時說明數(shu)組中不存在滿足條件的數(shu)字(zi)對,返回一個(ge)空(kong)數(shu)組。
代碼實現:
function twoSum(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
return [nums[left], nums[right]];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}
// 示例輸入
const nums = [2, 7, 11, 15];
const target = 9;
// 調用函數并輸出結果
console.log(twoSum(nums, target));