一、面试问题

给定一个包含 n 个整数的数组 arr[]，以及一个目标值 target，任务是判断数组中是否存在一对元素，其和等于目标值。这个问题是 Two Sum（两数之和）问题的一种变体。

举例：

输入：arr[] = [0, -1, 2, -3, 1]，target = -2
输出：true
解释： 存在一对数 (1, -3)，它们的和等于给定目标值：1 + (-3) = -2。

输入：arr[] = [1, -2, 1, 0, 5]，target = 0
输出：false
解释： 没有任何一对数的和等于目标值。

二、【朴素方法】生成所有可能的数对 — 时间复杂度 O(n^2)，空间复杂度 O(1)

(一) 算法思路与步骤

最基础的方法是生成所有可能的数对，并检查其中是否有一对的和等于目标值。为了生成所有的数对，我们只需运行两个嵌套的循环。

(二) JavaScript

// 函数用于检查是否存在一对数，其和等于给定的目标值
function twoSum(arr, target) {
  let n = arr.length;

  // 遍历数组中的每一个元素
  for (let i = 0; i < n; i++) {

    // 对于每个元素 arr[i]，检查其后面的每个元素 arr[j]
    for (let j = i + 1; j < n; j++) {

      // 检查当前数对的和是否等于目标值
      if (arr[i] + arr[j] === target) {
        return true;
      }
    }
  }
  // 如果检查完所有可能的组合后仍未找到符合条件的数对
  return false;
}

// 测试代码
let arr = [0, -1, 2, -3, 1];
let target = -2;

if (twoSum(arr, target))
  console.log("true");
else 
  console.log("false");

(三) C++

#include <iostream>
#include <vector>
using namespace std;

// 函数用于检查是否存在一对数，其和等于给定的目标值
bool twoSum(vector<int> &arr, int target) {
    int n = arr.size();

    // 遍历数组中的每一个元素
    for (int i = 0; i < n; i++) {

        // 对于每个元素 arr[i]，检查其后面的每个元素 arr[j]
        for (int j = i + 1; j < n; j++) {

            // 检查当前数对的和是否等于目标值
            if (arr[i] + arr[j] == target) {
                return true;
            }
        }
    }

    // 如果检查完所有可能的组合后仍未找到符合条件的数对
    return false;
}

int main() {

    vector<int> arr = {0, -1, 2, -3, 1};
    int target = -2;

    // 调用 twoSum 函数并输出结果
    if(twoSum(arr, target))
        cout << "true";
    else
        cout << "false";

    return 0;
}

(四) C

#include <stdbool.h>
#include <stdio.h>

// 函数用于检查是否存在一对数，其和等于给定的目标值
bool twoSum(int arr[], int n, int target){

    // 遍历数组中的每一个元素
    for (int i = 0; i < n; i++){

        // 对于每个元素 arr[i]，检查其后面的每个元素 arr[j]
        for (int j = i + 1; j < n; j++){

            // 检查当前数对的和是否等于目标值
            if (arr[i] + arr[j] == target)
                return true;
        }
    }
    // 如果检查完所有可能的组合后仍未找到符合条件的数对
    return false;
}

int main(){

    int arr[] = {0, -1, 2, -3, 1};
    int target = -2;
    int n = sizeof(arr) / sizeof(arr[0]);

    // 调用 twoSum 函数并打印结果
    if (twoSum(arr, n, target))
        printf("true\n");
    else
        printf("false\n");

    return 0;
}

(五) JAVA

class GfG {

    // 函数用于检查是否存在一对数，其和等于给定的目标值
    static boolean twoSum(int[] arr, int target){
        int n = arr.length;

        // 遍历数组中的每一个元素
        for (int i = 0; i < n; i++) {

            // 对于每个元素 arr[i]，检查其后面的每个元素 arr[j]
            for (int j = i + 1; j < n; j++) {

                // 检查当前数对的和是否等于目标值
                if (arr[i] + arr[j] == target) {
                    return true;
                }
            }
        }

        // 如果检查完所有可能的组合后仍未找到符合条件的数对
        return false;
    }

    public static void main(String[] args){

        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        // 调用 twoSum 函数并打印结果
        if (twoSum(arr, target))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

(六) Python

# 函数用于检查是否存在一对数，其和等于给定的目标值
def twoSum(arr, target):
    n = len(arr)

    # 遍历数组中的每一个元素
    for i in range(n):

        # 对于每个元素 arr[i]，检查其后面的每个元素 arr[j]
        for j in range(i + 1, n):

            # 检查当前数对的和是否等于目标值
            if arr[i] + arr[j] == target:
                return True

    # 如果检查完所有可能的组合后仍未找到符合条件的数对
    return False

if __name__ == "__main__":
    arr = [0, -1, 2, -3, 1]
    target = -2

    if twoSum(arr, target):
        print("true")
    else:
        print("false")

(七) C#

using System;

class GfG {

    // 函数用于检查是否存在一对数，其和等于给定的目标值
    static bool twoSum(int[] arr, int target) {
        int n = arr.Length;

        // 遍历数组中的每一个元素
        for (int i = 0; i < n; i++) {

            // 对于每个元素 arr[i]，检查其后面的每个元素 arr[j]
            for (int j = i + 1; j < n; j++) {

                // 检查当前数对的和是否等于目标值
                if (arr[i] + arr[j] == target) {
                    return true;
                }
            }
        }

        // 如果检查完所有可能的组合后仍未找到符合条件的数对
        return false;
    }

    static void Main() {

        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        // 调用 twoSum 函数并打印结果
        if (twoSum(arr, target))
            Console.WriteLine("true");
        else 
            Console.WriteLine("false");
    }
}

输出：

true

时间复杂度：O(n^2)，因为使用了两个嵌套循环
空间复杂度：O(1)

三、【更优方法 1】排序加二分查找 — 时间复杂度 O(n*log(n))，空间复杂度 O(1)

(一) 算法思路与步骤

我们也可以使用二分查找来解决这个问题。众所周知，在有序数组中查找元素的时间复杂度是 O(log(n))。我们首先对数组进行排序。然后对于数组中的每个元素 arr[i]，计算它的补数（即 target - 当前元素），并使用二分查找在索引 i 之后的子数组中快速判断这个补数是否存在。如果找到补数，则返回 true；如果遍历所有元素后都未找到补数，则返回 false。

(二) JavaScript

// 执行二分查找的函数
function binarySearch(arr, left, right, target) {
  while (left <= right) {
    let mid = Math.floor(left + (right - left) / 2);

    if (arr[mid] === target)
      return true;
    if (arr[mid] < target)
      left = mid + 1;
    else
      right = mid - 1;
  }
  return false;
}

// 判断是否存在任意一对数字
// 它们的和等于给定的目标值
function twoSum(arr, target) {
  // 对数组进行排序
  arr.sort((a, b) => a - b);

  // 遍历数组中的每一个元素
  for (let i = 0; i < arr.length; i++) {
    let complement = target - arr[i];

    // 使用二分查找寻找补数
    if (binarySearch(arr, i + 1, arr.length - 1, complement))
      return true;
  }
  // 如果没有找到符合条件的数字对
  return false;
}

// 驱动代码
let arr = [0, -1, 2, -3, 1];
let target = -2;

if (twoSum(arr, target)) {
  console.log("true");
} else {
  console.log("false");
}

(三) C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 执行二分查找的函数
bool binarySearch(vector<int> &arr, int left, int right, int target){
    while (left <= right){
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return true;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return false;
}

// 判断是否存在任意一对数字
// 它们的和等于给定的目标值
bool twoSum(vector<int> &arr, int target){

    // 对数组进行排序
    sort(arr.begin(), arr.end());

    // 遍历数组中的每一个元素
    for (int i = 0; i < arr.size(); i++){
        int complement = target - arr[i];

        // 使用二分查找寻找补数
        if (binarySearch(arr, i + 1, arr.size() - 1, complement))
            return true;
    }

    // 如果没有找到符合条件的数字对
    return false;
}

int main(){
    vector<int> arr = {0, -1, 2, -3, 1};
    int target = -2;

    if (twoSum(arr, target))
        cout << "true";
    else
        cout << "false";

    return 0;
}

(四) C

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于qsort排序
int compare(const void *a, const void *b){
    return (*(int *)a - *(int *)b);
}

// 执行二分查找的函数
bool binarySearch(int arr[], int left, int right, int target){
    while (left <= right){
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return true;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return false;
}

// 判断是否存在任意一对数字
// 它们的和等于给定的目标值
bool twoSum(int arr[], int n, int target){
    // 对数组进行排序
    qsort(arr, n, sizeof(int), compare);

    // 遍历数组中的每一个元素
    for (int i = 0; i < n; i++){
        int complement = target - arr[i];

        // 使用二分查找寻找补数
        if (binarySearch(arr, i + 1, n - 1, complement))
            return true;
    }
    // 如果没有找到符合条件的数字对
    return false;
}

int main(){
    int arr[] = {0, -1, 2, -3, 1};
    int target = -2;
    int n = sizeof(arr) / sizeof(arr[0]);

    if (twoSum(arr, n, target))
        printf("true\n");
    else
        printf("false\n");

    return 0;
}

(五) JAVA

import java.util.Arrays;

class GfG {

    // 执行二分查找的函数
    static boolean binarySearch(int[] arr, int left,
                                int right, int target){
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target)
                return true;
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }

    // 判断是否存在任意一对数字
    // 它们的和等于给定的目标值
    static boolean twoSum(int[] arr, int target){

        // 对数组进行排序
        Arrays.sort(arr);

        // 遍历数组中的每一个元素
        for (int i = 0; i < arr.length; i++) {
            int complement = target - arr[i];

            // 使用二分查找寻找补数
            if (binarySearch(arr, i + 1, arr.length - 1,
                             complement))
                return true;
        }
        // 如果没有找到符合条件的数字对
        return false;
    }

    public static void main(String[] args){
        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        if (twoSum(arr, target)) {
            System.out.println("true");
        }
        else {
            System.out.println("false");
        }
    }
}

(六) Python

# Function to perform binary search
def binary_search(arr, left, right, target):
    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

# Function to check whether any pair exists
# whose sum is equal to the given target value
def twoSum(arr, target):
    arr.sort()

    # Iterate through each element in the array
    for i in range(len(arr)):
        complement = target - arr[i]

        # Use binary search to find the complement
        if binary_search(arr, i + 1, len(arr) - 1, complement):
            return True
    # If no pair is found
    return False
  	
if __name__ == "__main__":
    arr = [0, -1, 2, -3, 1]
    target = -2

    if twoSum(arr, target):
        print("true")
    else:
        print("false")

(七) C#

using System;

class GfG {

    // 执行二分查找的函数
    static bool binarySearch(int[] arr, int left, int right,
                             int target){
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target)
                return true;
            if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }

    // 判断是否存在任意一对数字
    // 它们的和等于给定的目标值
    static bool twoSum(int[] arr, int target){
        // 对数组进行排序
        Array.Sort(arr);

        // 遍历数组中的每一个元素
        for (int i = 0; i < arr.Length; i++) {
            int complement = target - arr[i];

            // 使用二分查找寻找补数
            if (binarySearch(arr, i + 1, arr.Length - 1,
                             complement))
                return true;
        }
        // 如果没有找到符合条件的数字对
        return false;
    }

    static void Main(){
        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        if (twoSum(arr, target)) {
            Console.WriteLine("true");
        }
        else {
            Console.WriteLine("false");
        }
    }
}

四、【更优方法 2】排序加双指针技巧 — 时间复杂度 O(n*log(n))，空间复杂度 O(1)

思路是使用双指针技巧，但使用双指针技巧前，数组必须是已排序的。数组排序后，我们可以用这种方法：一个指针指向数组开头（左指针），另一个指针指向数组末尾（右指针）。然后检查这两个指针所指元素的和：

• 如果和等于目标值，说明找到了符合条件的数对。
• 如果和小于目标值，左指针向右移动以增加和。
• 如果和大于目标值，右指针向左移动以减小和。

(一) 算法思路与步骤

(二) JavaScript

// 函数：检查是否存在任意一对元素，其和等于目标值
function twoSum(arr, target)
{
    // 对数组进行排序
    arr.sort((a, b) => a - b);

    let left = 0, right = arr.length - 1;

    // 当左指针小于右指针时进行遍历
    while (left < right) {
        let sum = arr[left] + arr[right];

        // 检查当前两个元素的和是否等于目标值
        if (sum === target)
            return true;
        else if (sum < target)
            left++; // 和小于目标值，左指针右移
        else
            right--; // 和大于目标值，右指针左移
    }
    // 如果没有找到满足条件的元素对
    return false;
}

let arr = [ 0, -1, 2, -3, 1 ];
let target = -2;

// 调用 twoSum 函数并打印结果
if (twoSum(arr, target)) {
    console.log("true");
} else {
    console.log("false");
}

(三) C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 函数：检查是否存在任意一对元素，其和等于目标值
bool twoSum(vector<int> &arr, int target){
  
    // 对数组进行排序
    sort(arr.begin(), arr.end());

    int left = 0, right = arr.size() - 1;

    // 当左指针小于右指针时进行遍历
    while (left < right){
        int sum = arr[left] + arr[right];

        // 检查当前两个元素的和是否等于目标值
        if (sum == target)
            return true;
        else if (sum < target)
            left++; // 和小于目标值，左指针右移
        else
            right--; // 和大于目标值，右指针左移
    }
    // 如果没有找到满足条件的元素对
    return false;
}

int main(){
    vector<int> arr = {0, -1, 2, -3, 1};
    int target = -2;

    // 调用 twoSum 函数并打印结果
    if (twoSum(arr, target))
        cout << "true";
    else
        cout << "false";

    return 0;
}

(四) C

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

// qsort的比较函数
int compare(const void *a, const void *b){
    return (*(int *)a - *(int *)b);
}

// 函数：检查是否存在任意一对元素，其和等于目标值
bool twoSum(int arr[], int n, int target){
    // 对数组进行排序
    qsort(arr, n, sizeof(int), compare);

    int left = 0, right = n - 1;

    // 当左指针小于右指针时进行遍历
    while (left < right){
        int sum = arr[left] + arr[right];

        // 检查当前两个元素的和是否等于目标值
        if (sum == target)
            return true;
        else if (sum < target)
            left++; // 和小于目标值，左指针右移
        else
            right--; // 和大于目标值，右指针左移
    }
    // 如果没有找到满足条件的元素对
    return false;
}

int main(){
    int arr[] = {0, -1, 2, -3, 1};
    int target = -2;
    int n = sizeof(arr) / sizeof(arr[0]);

    // 调用 twoSum 函数并打印结果
    if (twoSum(arr, n, target))
        printf("true\n"); 
    else
        printf("false\n");

    return 0;
}

(五) JAVA

import java.util.Arrays;

class GfG {

    // 函数：检查是否存在任意一对元素，其和等于给定的目标值
    static boolean twoSum(int[] arr, int target){
        // 对数组进行排序
        Arrays.sort(arr);

        int left = 0, right = arr.length - 1;

        // 当左指针小于右指针时遍历
        while (left < right) {
            int sum = arr[left] + arr[right];

            // 检查当前元素和是否等于目标值
            if (sum == target)
                return true;
            else if (sum < target)
                left++; // 和小于目标值，左指针右移
            else
                right--; // 和大于目标值，右指针左移
        }
        // 如果没有找到满足条件的元素对
        return false;
    }

    public static void main(String[] args){
        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        // 调用 twoSum 函数并打印结果
        if (twoSum(arr, target)) {
            System.out.println("true");
        }
        else {
            System.out.println("false");
        }
    }
}

(六) Python

# 函数：检查是否存在任意一对元素，其和等于给定的目标值
def two_sum(arr, target):
    # 对数组进行排序
    arr.sort()

    left, right = 0, len(arr) - 1

    # 当左指针小于右指针时遍历
    while left < right:
        sum = arr[left] + arr[right]

        # 检查当前元素和是否等于目标值
        if sum == target:
            return True
        elif sum < target: 
            left += 1  # 和小于目标值，左指针右移
        else:
            right -= 1 # 和大于目标值，右指针左移

    # 如果没有找到满足条件的元素对
    return False

arr = [0, -1, 2, -3, 1]
target = -2

# 调用 two_sum 函数并打印结果
if two_sum(arr, target):
    print("true")
else:
    print("false")

(七) C#

using System;
using System.Linq;

class GfG {

    // 函数用于检查是否存在一对数
    // 它们的和等于给定的目标值
    static bool TwoSum(int[] arr, int target){
      
        // 对数组进行排序
        Array.Sort(arr);

        int left = 0, right = arr.Length - 1;

        // 当左指针小于右指针时迭代
        while (left < right) {
            int sum = arr[left] + arr[right];

            // 检查和是否等于目标值
            if (sum == target)
                return true;
            else if (sum < target)
                left++; // 将左指针向右移动
            else
                right--; // 将右指针向左移动
        }
        // 如果没有找到满足条件的数对
        return false;
    }

    static void Main(){
        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        // 调用 TwoSum 函数并输出结果
        if (TwoSum(arr, target))
            Console.WriteLine("true");
        else 
            Console.WriteLine("false");
    }
}

输出：

true

• 时间复杂度 (Time Complexity): O(n log n)，主要开销来自对数组的排序操作。
• 空间复杂度 (Auxiliary Space): O(1)，双指针方法在排序后只使用了常数级别的额外空间。

注意：这种方法是针对已排序数组的最佳方法。但如果数组未排序，则应使用下面的方法。

五、【推荐方法】使用哈希集合 — 时间复杂度 O(n)，空间复杂度 O(n)

(一) 算法思路与步骤

哈希法为2Sum问题提供了更高效的解决方案。我们不再检查所有可能的数对，而是在遍历数组元素时，将每个数字存入一个无序集合中。对于每个数字，我们计算其补数（即目标值减去当前数字），并检查该补数是否存在于集合中。如果存在，则说明找到了和为目标值的数对。该方法显著降低了时间复杂度，使我们能够在线性时间 O(n) 内解决该问题。

步骤方法：

1. 创建一个空的哈希集合（Hash Set）或无序集合（Unordered Set）。
2. 遍历数组，对于数组中的每个数字：

• 计算补数（target - 当前数字）。
• 检查补数是否存在于集合中：

• 如果存在，说明找到了满足条件的数对。
• 如果不存在，则将当前数字加入集合中。

3. 如果遍历结束仍未找到满足条件的数对，则返回不存在这样的数对。

(二) JavaScript

// 函数用于检查是否存在一对数字
// 其和等于给定的目标值
function twoSum(arr, target) {

    // 创建一个集合来存储元素
    let set = new Set();

    // 遍历数组中的每个元素
    for (let num of arr) {
    
        // 计算补数，即与当前数字相加
        // 等于目标值的数
        let complement = target - num;

        // 检查补数是否存在于集合中
        if (set.has(complement)) {
            return true;
        }

        // 将当前元素添加到集合中
        set.add(num);
    }
    // 如果没有找到满足条件的数对
    return false;
}

let arr = [0, -1, 2, -3, 1];
let target = -2;

// 调用 twoSum 函数并打印结果
if (twoSum(arr, target))
    console.log("true");
else 
    console.log("false");

(三) C++

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// 函数用于检查是否存在一对数字
// 其和等于给定的目标值
bool twoSum(vector<int> &arr, int target){
  
    // 创建一个无序集合用于存储元素
    unordered_set<int> s;

    // 遍历向量中的每个元素
    for (int i = 0; i < arr.size(); i++){

        // 计算补数，即与当前数字相加
        // 等于目标值的数
        int complement = target - arr[i];

        // 检查补数是否存在于集合中
        if (s.find(complement) != s.end())
            return true;

        // 将当前元素插入集合
        s.insert(arr[i]);
    }
  
    // 如果没有找到满足条件的数对
    return false;
}

int main(){
    vector<int> arr = {0, -1, 2, -3, 1};
    int target = -2;

    if (twoSum(arr, target))
        cout << "true";
    else
        cout << "false";

    return 0;
}

(四) JAVA

import java.util.HashSet;

class GfG {

    /**
     * 判断数组中是否存在两个数之和等于目标值
     * 时间复杂度：O(n)，只需遍历数组一次
     * 空间复杂度：O(n)，用于存储哈希集合中的元素
     *
     * @param arr    输入数组
     * @param target 目标和
     * @return 是否存在满足条件的两个数
     */
    static boolean twoSum(int[] arr, int target){

        // 创建HashSet存储元素
        HashSet<Integer> set = new HashSet<>();

        // 遍历数组中的每个元素
        for (int i = 0; i < arr.length; i++) {

            // 计算目标和与当前元素的差值
            int complement = target - arr[i];

            // 判断差值是否已经存在于HashSet中
            if (set.contains(complement)) {
                return true;
            }

            // 当前元素加入HashSet
            set.add(arr[i]);
        }
        // 未找到符合条件的两个数
        return false;
    }

    public static void main(String[] args){

        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        // 调用twoSum函数并输出结果
        if (twoSum(arr, target))
            System.out.println("true");  // 输出：true
        else
            System.out.println("false");
    }
}

(五) Python

# 函数用于检查是否存在一对数字
# 其和等于给定的目标值
def twoSum(arr, target):
  
    # 创建一个集合用于存储元素
    s = set()

    # 遍历数组中的每个元素
    for num in arr:
      
        # 计算补数，即与当前数字相加
        # 等于目标值的数
        complement = target - num

        # 检查补数是否存在于集合中
        if complement in s:
            return True

        # 将当前元素加入集合
        s.add(num)

    # 如果没有找到满足条件的数对
    return False

arr = [0, -1, 2, -3, 1]
target = -2

# 调用twoSum函数并打印结果
if twoSum(arr, target):
    print("true")
else:
    print("false")

(六) C#

using System;
using System.Collections.Generic;

class GfG {

    // 函数用于检查是否存在一对数字
    // 其和等于给定的目标值
    static bool TwoSum(int[] arr, int target){

        // 创建一个HashSet用于存储元素
        HashSet<int> set = new HashSet<int>();

        // 遍历数组中的每个元素
        for (int i = 0; i < arr.Length; i++) {

            // 计算补数，即与当前数字相加
            // 等于目标值的数
            int complement = target - arr[i];

            // 检查补数是否存在于HashSet中
            if (set.Contains(complement))
                return true;

            // 将当前元素加入HashSet
            set.Add(arr[i]);
        }
        // 如果没有找到满足条件的数对
        return false;
    }

    static void Main(){
        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        // 调用TwoSum函数并打印结果
        if (TwoSum(arr, target))
            Console.WriteLine("true");
        else 
            Console.WriteLine("false"); 
    }
}

输出

true

时间复杂度：O(n)，因为只需遍历数组一次。

空间复杂度：O(n)，用于存储哈希集合中的元素。

--THE END--