用100道题拿下你的算法面试（001）：两数之和，找出给定和的数对

欢迎大家来到IT世界,在知识的湖畔探索吧!

欢迎大家来到IT世界,在知识的湖畔探索吧!

一、面试问题

给定一个包含 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²)，空间复杂度 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"); 

欢迎大家来到IT世界,在知识的湖畔探索吧!

(三) C++

欢迎大家来到IT世界,在知识的湖畔探索吧!#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

欢迎大家来到IT世界,在知识的湖畔探索吧!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#

欢迎大家来到IT世界,在知识的湖畔探索吧!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²)，因为使用了两个嵌套循环
空间复杂度：O(1)

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

(一) 算法思路与步骤

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

(二) JavaScript

欢迎大家来到IT世界,在知识的湖畔探索吧!// 执行二分查找的函数 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

欢迎大家来到IT世界,在知识的湖畔探索吧!#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

欢迎大家来到IT世界,在知识的湖畔探索吧!# 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

欢迎大家来到IT世界,在知识的湖畔探索吧!// 函数：检查是否存在任意一对元素，其和等于目标值 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

欢迎大家来到IT世界,在知识的湖畔探索吧!#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

欢迎大家来到IT世界,在知识的湖畔探索吧!# 函数：检查是否存在任意一对元素，其和等于给定的目标值 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"); } } 

输出：

欢迎大家来到IT世界,在知识的湖畔探索吧!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++

欢迎大家来到IT世界,在知识的湖畔探索吧!#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

欢迎大家来到IT世界,在知识的湖畔探索吧!# 函数用于检查是否存在一对数字 # 其和等于给定的目标值 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"); } }

输出

欢迎大家来到IT世界,在知识的湖畔探索吧!true

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

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

–THE END–