算法题/双指针：给定数对的和

题目

给定一个有序数字数组和一个目标和，在数组中找到一对和等于给定目标的数字。写一个函数返回两个数字(即一对)的索引，使它们加起来等于给定的目标。
示例1：

输入：[1, 2, 3, 4, 6], target=6
输出：[1, 3]
解释：索引位置为1和为3上的数字之和为6: 2+4=6

示例2：

输入：[2, 5, 9, 11], target=11
输出：[0, 2]
解释：索引位置为0和为2上的数字之和为11: 0+2=11

解法1：双指针

Java

class PairWithTargetSum {

  public static int[] search(int[] arr, int targetSum) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
      int currentSum = arr[left] + arr[right];
      if (currentSum == targetSum)
        return new int[] { left, right };

      if (targetSum > currentSum)
        left++;
      else
        right--;
    }
    return new int[] { -1, -1 };
  }

  public static void main(String[] args) {
    int[] result = PairWithTargetSum.search(new int[] { 1, 2, 3, 4, 6 }, 6);
    System.out.println("Pair with target sum: [" + result[0] + ", " + result[1] + "]");
    result = PairWithTargetSum.search(new int[] { 2, 5, 9, 11 }, 11);
    System.out.println("Pair with target sum: [" + result[0] + ", " + result[1] + "]");
  }
}

JavaScript

class PairWithTargetSum {
  static search(arr, targetSum) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
      let currentSum = arr[left] + arr[right];
      if (currentSum === targetSum)
        return [left, right]; // found the pair

      if (targetSum > currentSum)
        left++; // we need a pair with a bigger sum
      else
        right--; // we need a pair with a smaller sum
    }
    return [-1, -1];
  }
}

let result = PairWithTargetSum.search([1, 2, 3, 4, 6], 6);
console.log("Pair with target sum: [" + result[0] + ", " + result[1] + "]");
result = PairWithTargetSum.search([2, 5, 9, 11], 11);
console.log("Pair with target sum: [" + result[0] + ", " + result[1] + "]");

Python

class PairWithTargetSum:
    def search(arr, targetSum):
        left = 0
        right = len(arr) - 1
        while left < right:
            currentSum = arr[left] + arr[right]
            if currentSum == targetSum:
                return [left, right]  
            if targetSum > currentSum:
                left += 1  
            else:
                right -= 1  
        return [-1, -1]

result = PairWithTargetSum.search([1, 2, 3, 4, 6], 6)
print("Pair with target sum:", result)
result = PairWithTargetSum.search([2, 5, 9, 11], 11)
print("Pair with target sum:", result)

Go

package main

import "fmt"

type PairWithTargetSum struct{}

func (p *PairWithTargetSum) search(arr []int, targetSum int) []int {
	left := 0
	right := len(arr) - 1
	for left < right {
		currentSum := arr[left] + arr[right]
		if currentSum == targetSum {
			return []int{left, right} 
		}
		if targetSum > currentSum {
			left++ 
		} else {
			right-- 
		}
	}
	return []int{-1, -1}
}

func main() {
	p := &PairWithTargetSum{}
	result := p.search([]int{1, 2, 3, 4, 6}, 6)
	fmt.Printf("Pair with target sum: [%d, %d]\n", result[0], result[1])
	result = p.search([]int{2, 5, 9, 11}, 11)
	fmt.Printf("Pair with target sum: [%d, %d]\n", result[0], result[1])
}