导入
三数之和
给定一个整数数组和一个值，判断数组中是否存在三个整数，使得它们的和等于给定的值。
题目
给定一个整数数组和一个整数值，判断数组中是否存在任意三个整数，其和等于给定的值。如果找到这样的三个整数，则返回 true；否则返回 false。
示例
考虑以下数组和目标和：
...
示例输入
1([3, 7, 1, 2, 8, 4, 5], 20)
期望输出
1true
自行尝试
多标签代码
C++
1#include <iostream> 2#include <vector> 3 4using namespace std; 5 6bool FindSumOfThree(vector<int> nums, int required_sum) { 7 // TODO: 写你的代码 8 return false; 9}
Java
1// 导入所需函数 2import java.util.*; 3 4class SumOfThree { 5 public static boolean findSumOfThree(int nums[], int sum) { 6 // TODO: 写你的代码 7 return false; 8 } 9}
Python
1def find_sum_of_three(nums, required_sum): 2 # TODO: 写你的代码 3 return False
JS
1let findSumOfThree = function(arr, sum) { 2 // TODO: 写你的代码 3 return false; 4};
Ruby
1def find_sum_of_three(nums, required_sum) 2 # TODO: 写你的代码 3 return false 4end
Go
1package main 2import ( 3 "fmt" 4 "sort" 5 "strconv" 6 "encoding/json" 7) 8 9func FindSumOfThree(Nums []int, RequiredSum int) bool { 10 // TODO: 写你的代码 11 return false 12}
解法 1
最简单直接的方法是使用三重嵌套循环遍历所有无序三元组，检查它们的和是否等于给定的整数。虽然这种方法可行，但效率不高。
存在其他时间复杂度更优的解法。我们将在本课后续部分介绍这些方法。
多标签代码
C++
1#include <iostream> 2#include <vector> 3 4using namespace std; 5 6bool FindSumOfThree(vector<int> nums, int required_sum) { 7 // 用于存储当前元素和的变量 8 int sum = 0; 9 for (int i = 0; i < nums.size() - 2; ++i) { 10 for (int j = i + 1; j < nums.size() - 1; ++j) { 11 for (int k = j + 1; k < nums.size(); ++k) { 12 // i, j, k 是索引，用于避免重复使用同一数组元素计算和的情况。 13 if ((i != j) && (j != k) && (k != i)) { 14 sum = nums[i] + nums[j] + nums[k]; 15 if (sum == required_sum) { 16 return true; 17 } 18 } 19 } 20 } 21 } 22 return false; 23} 24 25int main() { 26 vector<int> nums_1 = {3, 7, 1, 2, 8, 4, 5}; 27 vector<int> test_list_1 = {10, 20, 21}; 28 29 cout << "1. 原始数组: "; 30 // 自定义 PrintList 函数打印向量 31 PrintList(nums_1); 32 for (int test : test_list_1) { 33 if (FindSumOfThree(nums_1, test)) { 34 cout << " 和为 " << test << " 的组合存在" << endl; 35 } else { 36 cout << " 和为 " << test << " 的组合不存在" << endl; 37 } 38 } 39 cout << "--------------------------------------------------------------------" 40 "----------------------------------\n" 41 << endl; 42 43 vector<int> nums_2 = {-1, 2, 1, -4, 5, -3}; 44 vector<int> test_list_2 = {-8, 0, 7}; 45 46 cout << "2. 原始数组: "; 47 // 自定义 PrintList 函数打印向量 48 PrintList(nums_2); 49 for (int test : test_list_2) { 50 if (FindSumOfThree(nums_2, test)) { 51 cout << " 和为 " << test << " 的组合存在" << endl; 52 } else { 53 cout << " 和为 " << test << " 的组合不存在" << endl; 54 } 55 } 56 cout << "------------------------------------------------------------------------------------------------------\n"<< endl; 57}
Java
1// 导入所需函数 2import java.util.*; 3 4class SumOfThree { 5 public static boolean findSumOfThree(int arr[], int requiredSum) { 6 for (int i = 0; i < arr.length - 2; i++) { 7 for (int j = i + 1; j < arr.length - 1; j++) { 8 for (int k = j + 1; k < arr.length; k++) { 9 // i, j, k 是索引，用于避免重复使用同一数组元素计算和的情况。 10 if ((i != j) && (j != k) && (k != i)) { 11 // 用于存储当前元素和的变量 12 int sum = arr[i] + arr[j] + arr[k]; 13 if (sum == requiredSum) { 14 return true; 15 } 16 } 17 } 18 } 19 } 20 return false; 21 } 22 23 public static void main(String[] args) { 24 int[] nums_1 = {3, 7, 1, 2, 8, 4, 5}; 25 int[] test_list_1 = {10, 20, 21}; 26 27 System.out.println("1. 原始数组: " + Arrays.toString(nums_1)); 28 for (int test : test_list_1) { 29 if (findSumOfThree(nums_1, test)) { 30 System.out.println(" 和为 " + test + " 的组合存在"); 31 } else { 32 System.out.println(" 和为 " + test + " 的组合不存在"); 33 } 34 } 35 System.out.println( 36 "------------------------------------------------------------------------------------------------------\n"); 37 38 int[] nums_2 = {-1, 2, 1, -4, 5, -3}; 39 int[] test_list_2 = {-8, 0, 7}; 40 41 System.out.println("2. 原始数组: " + Arrays.toString(nums_2)); 42 for (int test : test_list_2) { 43 if (findSumOfThree(nums_2, test)) { 44 System.out.println(" 和为 " + test + " 的组合存在"); 45 } else { 46 System.out.println(" 和为 " + test + " 的组合不存在"); 47 } 48 } 49 System.out.println( 50 "------------------------------------------------------------------------------------------------------\n"); 51 } 52}
Python
1def find_sum_of_three(nums, required_sum): 2 # 用于存储当前元素和的变量 3 for i in range(0, len(nums)-2): 4 for j in range(i+1, len(nums)-1): 5 for k in range(j+1, len(nums)): 6 # i, j, k 是索引，用于避免重复使用同一数组元素计算和的情况。 7 if i != j and j != k and k != i: 8 sum_ = nums[i] + nums[j] + nums[k] 9 if sum_ == required_sum: 10 return True 11 return False 12 13def main(): 14 nums_lists = [[3, 7, 1, 2, 8, 4, 5], [-1, 2, 1, -4, 5, -3]] 15 test_lists = [[10, 20, 21], [-8, 0, 7]] 16 17 for i in range(len(nums_lists)): 18 print(str(i+1) + ". 原始数组:", str(nums_lists[i])) 19 for j in range(len(test_lists[i])): 20 if find_sum_of_three(nums_lists[i], test_lists[i][j]): 21 print(" 和为", test_lists[i][j], "的组合存在") 22 else: 23 print(" 和为", test_lists[i][j], "的组合不存在") 24 print("------------------------------------------------------------------------------------------------------\n") 25 26 27if __name__ == '__main__': 28 main()
JS
1let findSumOfThree = function(nums, requiredSum) { 2 3 // 用于存储当前元素和的变量 4 let sum =0; 5 for (let i = 0; i < nums.length - 2; ++i) { 6 for (let j = i + 1; j < nums.length - 1; ++j) { 7 for (let k = j + 1; k < nums.length; ++k) { 8 9 // i,j 和 k 是索引，用于避免重复使用同一数组元素计算和的情况。 10 if (i != j && j != k && k != i) { 11 sum = nums[i] + nums[j] + nums[k]; 12 if (sum === requiredSum) { 13 return true; 14 } 15 } 16 } 17 } 18 } 19 return false; 20}; 21 22let nums1 = [3, 7, 1, 2, 8, 4, 5]; 23let testList1 = [10, 20, 21]; 24 25console.log("1. 原始数组: " + printArray(nums1)); 26for (let test of testList1) { 27 if (findSumOfThree(nums1, test)) { 28 console.log(" 和为 " + test + " 的组合存在 "); 29 } else { 30 console.log(" 和为 " + test + " 的组合不存在 "); 31 } 32} 33console.log( 34 "------------------------------------------------------------------------------------------------------\n"); 35 36let nums2 = [-1, 2, 1, -4, 5, -3]; 37let testList2 = [-8, 0, 7]; 38 39console.log("2. 原始数组: " + printArray(nums2)); 40for (let test of testList2) { 41 if (findSumOfThree(nums2, test)) { 42 console.log(" 和为 " + test + " 的组合存在 "); 43 } else { 44 console.log(" 和为 " + test + " 的组合不存在 "); 45 } 46} 47console.log( 48 "------------------------------------------------------------------------------------------------------\n");
Ruby
1def find_sum_of_three(nums, required_sum) 2 for i in 0 .. nums.length - 3 3 for j in i + 1 .. nums.length - 2 4 for k in j + 1 .. nums.length - 1 5 # i,j, k 是索引，用于避免重复使用同一数组元素计算和的情况。 6 if i != j and j != k and k != i 7 sum = nums[i] + nums[j] + nums[k] 8 return true if sum == required_sum 9 end 10 end 11 end 12 end 13 return false 14end 15 16nums_lists = [[3, 7, 1, 2, 8, 4, 5], [-1, 2, 1, -4, 5, -3]] 17test_lists = [[10, 20, 21], [-8, 0, 7]] 18 19nums_lists.length.times do |i| 20 print (i + 1).to_s + ". 原始数组: " + nums_lists[i].to_s 21 test_lists[i].length.times do |j| 22 if find_sum_of_three(nums_lists[i], test_lists[i][j]) 23 print "\n 和为 " + test_lists[i][j].to_s + " 的组合存在" 24 else 25 print "\n 和为 "+ test_lists[i][j].to_s + " 的组合不存在" 26 end 27 end 28 print "\n------------------------------------------------------------------------------------------------------\n" 29end
Go
1package main 2import ( 3 "fmt" 4 "strconv" 5) 6 7// FindSumOfThree 是我们的挑战函数 8func FindSumOfThree(Nums []int, RequiredSum int) bool { 9 // 用于存储当前元素和的变量 10 for i := 0; i < len(Nums) - 2; i++ { 11 for j := i + 1; j < len(Nums) - 1; j++ { 12 for k := j + 1; k < len(Nums); k++ { 13 // i, j, k 是索引，用于避免重复使用同一数组元素计算和的情况。 14 if i != j && j != k && (j != k && k != i) { 15 Sum := Nums[i] + Nums[j] + Nums[k] 16 if Sum == RequiredSum { 17 return true 18 } 19 } 20 } 21 } 22 } 23 return false 24} 25 26/* ArrayToString 用于将整数数组转换为字符串。 27ArrayToString 作为辅助函数在主函数中用于打印目的。 */ 28func ArrayToString(nums []int) string{ 29 if len(nums) == 0 { 30 return "[]" 31 } 32 res := "[" 33 for _, num := range nums { 34 res += strconv.Itoa(num) + ", " 35 } 36 res += "]" 37 return res[:len(res) - 3] + "]" 38} 39 40func main() { 41 NumsLists := [][]int{{3, 7, 1, 2, 8, 4, 5}, {-1, 2, 1, -4, 5, -3}} 42 TestLists := [][]int{{10, 20, 21}, {-8, 0, 7}} 43 for i, nList := range NumsLists { 44 fmt.Printf("%d. 原始数组: %s\n", i + 1, ArrayToString(nList)) 45 for _, tList := range TestLists[i] { 46 if FindSumOfThree(nList, tList) { 47 fmt.Printf(" 和为 %d 的组合存在\n", tList) 48 } else { 49 fmt.Printf(" 和为 %d 的组合不存在\n", tList) 50 } 51 } 52 fmt.Print("------------------------------------------------------------------------------------------------------\n") 53 } 54}
时间复杂度
此解法的时间复杂度为立方级，。
空间复杂度
此解法的空间复杂度为常数级，。
解法 2
我们可以先将输入数组排序，耗时 。然后从数组的第一个元素开始，用索引 i 遍历每个元素。在嵌套循环中，使用两个指针 low 和 high 来遍历数组，寻找满足 nums[low] + nums[high] + nums[i] 等于所需 sum 的三元组。
- 如果三数之和等于所需和，则找到解。
- 否则，如果三数之和大于所需和，则将
high指针向前移动。 - 否则，如果三数之和小于所需和，则将
low指针向后移动。
我们通过固定不同元素在索引 i 处来重复此过程。
让我们看看该算法如何应用于上述示例：
[图示可视化]
补充思考
当我们对数组进行排序时，会改变原始数组本身。如果我们不允许修改输入数组，可以使用哈希表来达到相同的时间复杂度。然而，这需要 的额外内存。
另一种替代方案是创建输入数组的副本并对其进行排序，而不是对原数组排序。
多标签代码
C++
1#include <iostream> 2#include <vector> 3#include <algorithm> 4 5using namespace std; 6 7bool FindSumOfThree(vector<int> nums, int required_sum) { 8 // 对输入向量进行排序 9 sort(nums.begin(), nums.end()); 10 11 // 创建两个指针来跟踪我们的索引 12 // 以及一个变量来存储三元组的和 13 int low, high, triples; 14 15 // 逐个固定一个元素，并寻找另外两个 16 for (int i = 0; i < nums.size() - 2; i++) { 17 // 设置两个指针的索引 18 19 // 剩余元素中第一个元素的索引 20 low = i + 1; 21 22 // 最后一个索引 23 high = nums.size() - 1; 24 25 while (low < high) { 26 // 检查三元组是否等于和 27 triples = nums[i] + nums[low] + nums[high]; 28 if (triples == required_sum) { 29 return true; 30 } 31 // 如果三元组和小于所需和，则向前移动 low 指针 32 else if (triples < required_sum) { 33 low++; 34 } // 如果三元组和大于所需和，则向后移动 high 指针 35 else { 36 high--; 37 } 38 } 39 } 40 return false; 41} 42 43int main() { 44 vector<int> nums_1 = {3, 7, 1, 2, 8, 4, 5}; 45 vector<int> test_list_1 = {10, 20, 21}; 46 47 cout << "1. 原始数组: "; 48 // 自定义 PrintList 函数打印向量 49 PrintList(nums_1); 50 for (int test : test_list_1) { 51 if (FindSumOfThree(nums_1, test)) { 52 cout << " 和为 " << test << " 的组合存在" << endl; 53 } else { 54 cout << " 和为 " << test << " 的组合不存在" << endl; 55 } 56 } 57 cout << "------------------------------------------------------------------------------------------------------\n" << endl; 58 59 vector<int> nums_2 = {-1, 2, 1, -4, 5, -3}; 60 vector<int> test_list_2 = {-8, 0, 7}; 61 62 cout << "2. 原始数组: "; 63 // 自定义 PrintList 函数打印向量 64 PrintList(nums_2); 65 for (int test : test_list_2) { 66 if (FindSumOfThree(nums_2, test)) { 67 cout << " 和为 " << test << " 的组合存在" << endl; 68 } else { 69 cout << " 和为 " << test << " 的组合不存在" << endl; 70 } 71 } 72 cout << "------------------------------------------------------------------------------------------------------\n" << endl; 73}
Java
1// 导入所需函数 2import java.util.*; 3 4class SumOfThree { 5 public static boolean findSumOfThree(int nums[], int requiredSum) { 6 // 对输入向量进行排序 7 Arrays.sort(nums); 8 9 // 创建两个指针来跟踪我们的索引 10 // 以及一个变量来存储三元组的和 11 int low, high, triples; 12 13 // 逐个固定一个元素，并寻找另外两个 14 for (int i = 0; i < nums.length - 2; i++) { 15 // 设置两个指针的索引 16 17 // 剩余元素中第一个元素的索引 18 low = i + 1; 19 20 // 最后一个索引 21 high = nums.length - 1; 22 23 while (low < high) { 24 // 检查三元组是否等于和 25 triples = nums[i] + nums[low] + nums[high]; 26 if (triples == requiredSum) { 27 return true; 28 } 29 // 如果三元组和小于所需和，则向前移动 low 指针 30 else if (triples < requiredSum) { 31 low++; 32 } // 如果三元组和大于所需和，则向后移动 high 指针 33 else { 34 high--; 35 } 36 } 37 } 38 return false; 39 } 40 41 public static void main(String[] args) { 42 int[] nums_1 = {3, 7, 1, 2, 8, 4, 5}; 43 int[] test_list_1 = {10, 20, 21}; 44 45 System.out.println("1. 原始数组: " + Arrays.toString(nums_1)); 46 for (int test : test_list_1) { 47 if (findSumOfThree(nums_1, test)) { 48 System.out.println(" 和为 " + test + " 的组合存在"); 49 } else { 50 System.out.println(" 和为 " + test + " 的组合不存在"); 51 } 52 } 53 System.out.println( 54 "------------------------------------------------------------------------------------------------------\n"); 55 56 int[] nums_2 = {-1, 2, 1, -4, 5, -3}; 57 int[] test_list_2 = {-8, 0, 7}; 58 59 System.out.println("2. 原始数组: " + Arrays.toString(nums_2)); 60 for (int test : test_list_2) { 61 if (findSumOfThree(nums_2, test)) { 62 System.out.println(" 和为 " + test + " 的组合存在"); 63 } else { 64 System.out.println(" 和为 " + test + " 的组合不存在"); 65 } 66 } 67 System.out.println( 68 "------------------------------------------------------------------------------------------------------\n"); 69 } 70}
Python
1def find_sum_of_three(nums, required_sum): 2 # 对输入向量进行排序 3 nums.sort() 4 5 # 逐个固定一个元素，并寻找另外两个 6 for i in range(0, len(nums)-2): 7 # 设置两个指针的索引 8 9 # 剩余元素中第一个元素的索引 10 low = i + 1 11 12 # 最后一个索引 13 high = len(nums) - 1 14 15 while low < high: 16 # 检查三元组是否等于和 17 triples = nums[i] + nums[low] + nums[high] 18 if triples == required_sum: 19 return True 20 # 如果三元组和小于所需和，则向前移动 low 指针 21 elif triples < required_sum: 22 low += 1 23 # 如果三元组和大于所需和，则向后移动 high 指针 24 else: 25 high -= 1 26 return False 27 28 29def main(): 30 nums_lists = [[3, 7, 1, 2, 8, 4, 5], [-1, 2, 1, -4, 5, -3]] 31 test_lists = [[10, 20, 21], [-8, 0, 7]] 32 33 for i in range(len(nums_lists)): 34 print(str(i+1) + ". 原始数组: ", str(nums_lists[i])) 35 for j in range(len(test_lists[i])): 36 if find_sum_of_three(nums_lists[i], test_lists[i][j]): 37 print(" 和为", test_lists[i][j], "的组合存在") 38 else: 39 print(" 和为", test_lists[i][j], "的组合不存在") 40 print("------------------------------------------------------------------------------------------------------\n") 41 42 43if __name__ == '__main__': 44 main()
JS
1let findSumOfThree = function(nums, required_sum) { 2 // 对输入向量进行排序 3 nums.sort(function(a, b) { 4 return a - b; 5 }); 6 7 // 创建两个指针来跟踪我们的索引 8 // 以及一个变量来存储三元组的和 9 var low, high, triples; 10 11 for (let i = 0; i < nums.length - 2; i++) { 12 // 设置两个指针的索引 13 // 剩余元素中第一个元素的索引 14 low = i + 1; 15 16 // 最后一个索引 17 high = nums.length-1; 18 19 while(low<high){ 20 // 检查三元组是否等于和 21 triples = nums[i] + nums[low] + nums[high]; 22 if (triples == required_sum) { 23 return true; 24 } 25 // 如果三元组和小于所需和，则向前移动 low 指针 26 else if (triples < required_sum) { 27 low++; 28 } // 如果三元组和大于所需和，则向后移动 high 指针 29 else { 30 high--; 31 } 32 } 33 34 } 35 return false; 36}; 37 38let nums1 = [3, 7, 1, 2, 8, 4, 5]; 39let testList1 = [10, 20, 21]; 40 41console.log("1. 原始数组: " + printArray(nums1)); 42for (let test of testList1) { 43 if (findSumOfThree(nums1, test)) { 44 console.log(" 和为 " + test + " 的组合存在 "); 45 } else { 46 console.log(" 和为 " + test + " 的组合不存在 "); 47 } 48} 49console.log( 50 "------------------------------------------------------------------------------------------------------\n"); 51 52let nums2 = [-1, 2, 1, -4, 5, -3]; 53let testList2 = [-8, 0, 7]; 54 55console.log("2. 原始数组: " + printArray(nums2)); 56for (let test of testList2) { 57 if (findSumOfThree(nums2, test)) { 58 console.log(" 和为 " + test + " 的组合存在 "); 59 } else { 60 console.log(" 和为 " + test + " 的组合不存在 "); 61 } 62} 63console.log( 64 "------------------------------------------------------------------------------------------------------\n");
Ruby
1# find_sum_of_three 是我们的挑战函数 2def find_sum_of_three(nums, required_sum) 3 # 对输入向量进行排序 4 nums.sort! 5 6 # 逐个固定一个元素，并寻找另外两个 7 for i in 0 .. nums.length - 2 8 # 设置两个指针的索引 9 # 剩余元素中第一个元素的索引 10 low = i + 1 11 12 # 最后一个索引 13 high = nums.length - 1 14 15 while low < high 16 # 检查三元组是否等于和 17 triples = nums[i] + nums[low] + nums[high] 18 if triples == required_sum 19 return true 20 # 如果三元组和小于所需和，则向前移动 low 指针 21 elsif triples < required_sum 22 low += 1 23 # 如果三元组和大于所需和，则向后移动 high 指针 24 else 25 high-=1 26 end 27 end 28 end 29 return false 30end 31 32# 主函数 33nums_lists = [[3, 7, 1, 2, 8, 4, 5], [-1, 2, 1, -4, 5, -3]] 34test_lists = [[10, 20, 21], [-8, 0, 7]] 35 36nums_lists.length.times do |i| 37 print (i + 1).to_s + ". 原始数组: " + nums_lists[i].to_s 38 test_lists[i].length.times do |j| 39 if find_sum_of_three(nums_lists[i], test_lists[i][j]) 40 print "\n 和为 " + test_lists[i][j].to_s + " 的组合存在" 41 else 42 print "\n 和为 "+ test_lists[i][j].to_s + " 的组合不存在" 43 end 44 end 45 print "\n------------------------------------------------------------------------------------------------------\n" 46end
Go
1package main 2 3import ( 4 "fmt" 5 "strconv" 6 "sort" 7) 8 9// FindSumOfThree 是我们的挑战函数 10func FindSumOfThree(nums []int, requiredSum int) bool { 11 // 对输入向量进行排序 12 sort.Sort(sort.IntSlice(nums)) 13 14 // 创建两个指针来跟踪我们的索引 15 // 以及一个变量来存储三元组的和 16 low, high, triples := 0, 0, 0 17 18 // 逐个固定一个元素，并寻找另外两个 19 for i := 0; i < len(nums) - 2; i++ { 20 // 设置两个指针的索引 21 22 // 剩余元素中第一个元素的索引 23 low = i + 1 24 25 // 最后一个索引 26 high = len(nums) - 1 27 28 for low < high { 29 // 检查三元组是否等于和 30 triples = nums[i] + nums[low] + nums[high] 31 if triples == requiredSum { 32 return true 33 34 // 如果三元组和小于所需和，则向前移动 low 指针 35 } else if triples < requiredSum { 36 low += 1 37 } else { 38 // 如果三元组和大于所需和，则向后移动 high 指针 39 high -= 1 40 } 41 } 42 } 43 return false 44} 45 46/* ArrayToString 用于将整数数组转换为字符串。 47ArrayToString 作为辅助函数在主函数中用于打印目的。 */ 48func ArrayToString(nums []int) string{ 49 if len(nums) == 0 { 50 return "[]" 51 } 52 res := "[" 53 for _, num := range nums { 54 res += strconv.Itoa(num) + ", " 55 } 56 res += "]" 57 return res[:len(res) - 3] + "]" 58} 59 60func main() { 61 numsLists := [][]int{{3, 7, 1, 2, 8, 4, 5}, {-1, 2, 1, -4, 5, -3}} 62 TestLists := [][]int{{10, 20, 21}, {-8, 0, 7}} 63 for i, nList := range numsLists { 64 fmt.Printf("%d. 原始数组: %s\n", i + 1, ArrayToString(nList)) 65 for _, tList := range TestLists[i] { 66 if FindSumOfThree(nList, tList) { 67 fmt.Printf(" 和为 %d 的组合存在\n", tList) 68 } else { 69 fmt.Printf(" 和为 %d 的组合不存在\n", tList) 70 } 71 } 72 fmt.Print("------------------------------------------------------------------------------------------------------\n") 73 } 74}
时间复杂度
此解法的时间复杂度为 。
空间复杂度
此解法的空间复杂度为常数级，。
解法 3
此解法使用哈希技术进一步简化算法。然而，它使用了额外的空间。
我们在此解法中使用嵌套循环。外层循环使用索引 i 从第一个元素遍历到倒数第二个元素，内层循环遍历从 i + 1 到末尾的元素。
在嵌套循环中，我们计算 nums[i] 和 nums[j] 元素的和。然后检查该和是否存在于我们的哈希表中。如果找到该和，说明已找到三元组，返回 true。否则，我们将该和加入哈希表并继续迭代。
多标签代码
C++
1#include <iostream> 2#include <vector> 3#include <unordered_set> 4 5using namespace std; 6 7bool FindSumOfThree(vector<int> nums, int required_sum) { 8 // 创建无序集合/哈希表 9 unordered_set<int> hashmap; 10 11 // 创建两个变量来跟踪当前和 12 // 以及存储所需的三元组 13 int current_sum, triple_needed; 14 15 // 逐个固定一个元素，并寻找另外两个 16 for (int i = 0; i < nums.size() - 1; i++) { 17 18 // 清空哈希表以供每次迭代使用 19 hashmap.clear(); 20 21 // 计算给定 nums[i] 所需的当前和 22 current_sum = required_sum - nums[i]; 23 24 for (int j = i + 1; j < nums.size(); j++) { 25 // 计算两个元素所需的三元组 26 triple_needed = current_sum - nums[j]; 27 28 // 检查所需的第三个元素是否存在于哈希表中 29 if (hashmap.find(triple_needed) != hashmap.end()) { 30 return true; 31 } 32 // 将当前元素添加到哈希表中 33 hashmap.insert(nums[j]); 34 } 35 } 36 return false; 37} 38 39int main() { 40 vector<int> nums_1 = {3, 7, 1, 2, 8, 4, 5}; 41 vector<int> test_list_1 = {10, 20, 21}; 42 43 cout << "1. 原始数组: "; 44 // 自定义 PrintList 函数打印向量 45 PrintList(nums_1); 46 for (int test : test_list_1) { 47 if (FindSumOfThree(nums_1, test)) { 48 cout << " 和为 " << test << " 的组合存在" << endl; 49 } else { 50 cout << " 和为 " << test << " 的组合不存在" << endl; 51 } 52 } 53 cout << "------------------------------------------------------------------------------------------------------\n" << endl; 54 55 vector<int> nums_2 = {-1, 2, 1, -4, 5, -3}; 56 vector<int> test_list_2 = {-8, 0, 7}; 57 58 cout << "2. 原始数组: "; 59 // 自定义 PrintList 函数打印向量 60 PrintList(nums_2); 61 for (int test : test_list_2) { 62 if (FindSumOfThree(nums_2, test)) { 63 cout << " 和为 " << test << " 的组合存在" << endl; 64 } else { 65 cout << " 和为 " << test << " 的组合不存在" << endl; 66 } 67 } 68 cout << "------------------------------------------------------------------------------------------------------\n" << endl; 69}
Java
1// 导入所需函数 2import java.util.*; 3 4class SumOfThree { 5 public static boolean findSumOfThree(int nums[], int requiredSum) { 6 // 创建无序集合/哈希集 7 HashSet<Integer> hashset = new HashSet<Integer>(); 8 9 // 创建两个变量来跟踪当前和 10 // 以及存储所需的三元组 11 int currentSum, tripleNeeded; 12 13 // 逐个固定一个元素，并寻找另外两个 14 for (int i = 0; i < nums.length - 1; i++) { 15 16 // 清空哈希集以供每次迭代使用 17 hashset.clear(); 18 19 // 计算给定 nums[i] 所需的当前和 20 currentSum = requiredSum - nums[i]; 21 22 for (int j = i + 1; j < nums.length; j++) { 23 // 计算两个元素所需的三元组 24 tripleNeeded = currentSum - nums[j]; 25 26 // 检查所需的第三个元素是否存在于哈希集中 27 if (hashset.contains(tripleNeeded)) { 28 return true; 29 } 30 // 将当前元素添加到哈希集中 31 hashset.add(nums[j]); 32 } 33 } 34 return false; 35 } 36 37 public static void main(String[] args) { 38 int[] nums_1 = {3, 7, 1, 2, 8, 4, 5}; 39 int[] test_list_1 = {10, 20, 21}; 40 41 System.out.println("1. 原始数组: " + Arrays.toString(nums_1)); 42 for (int test : test_list_1) { 43 if (findSumOfThree(nums_1, test)) { 44 System.out.println(" 和为 " + test + " 的组合存在"); 45 } else { 46 System.out.println(" 和为 " + test + " 的组合不存在"); 47 } 48 } 49 System.out.println( 50 "------------------------------------------------------------------------------------------------------\n"); 51 52 int[] nums_2 = {-1, 2, 1, -4, 5, -3}; 53 int[] test_list_2 = {-8, 0, 7}; 54 55 System.out.println("2. 原始数组: " + Arrays.toString(nums_2)); 56 for (int test : test_list_2) { 57 if (findSumOfThree(nums_2, test)) { 58 System.out.println(" 和为 " + test + " 的组合存在"); 59 } else { 60 System.out.println(" 和为 " + test + " 的组合不存在"); 61 } 62 } 63 System.out.println( 64 "------------------------------------------------------------------------------------------------------\n"); 65 } 66}
Python
1def find_sum_of_three(nums, required_sum): 2 # 创建无序集合/哈希表 3 hashmap = set() 4 5 # 逐个固定一个元素，并寻找另外两个 6 for i in range(len(nums)-1): 7 # 清空哈希表以供每次迭代使用 8 hashmap.clear() 9 10 # 计算给定 nums[i] 所需的当前和 11 current_sum = required_sum - nums[i] 12 13 for j in range(i + 1, len(nums)): 14 # 计算两个元素所需的三元组 15 triple_needed = current_sum - nums[j] 16 17 # 检查所需的第三个元素是否存在于哈希表中 18 if triple_needed in hashmap: 19 return True 20 # 将当前元素添加到哈希表中 21 hashmap.add(nums[j]) 22 return False 23 24def main(): 25 nums_lists = [[3, 7, 1, 2, 8, 4, 5], [-1, 2, 1, -4, 5, -3]] 26 test_lists = [[10, 20, 21], [-8, 0, 7]] 27 28 for i in range(len(nums_lists)): 29 print (str(i+1) + ". 原始数组:", str(nums_lists[i])) 30 for j in range(len(test_lists[i])): 31 if find_sum_of_three(nums_lists[i], test_lists[i][j]): 32 print(" 和为", test_lists[i][j], "的组合存在") 33 else: 34 print(" 和为", test_lists[i][j], "的组合不存在") 35 print("------------------------------------------------------------------------------------------------------\n") 36 37if __name__ == '__main__': 38 main()
JS
1let findSumOfThree = function(nums, requiredSum) { 2 3 // 创建无序集合/哈希表 4 let hashmap = new Set(); 5 6 // 创建两个变量来跟踪当前和 7 // 以及存储所需的三元组 8 let currentSum, tripleNeeded; 9 10 // 逐个固定一个元素，并寻找另外两个 11 for (let i = 0; i < nums.length - 1; i++) { 12 13 // 清空哈希表以供每次迭代使用 14 hashmap.clear(); 15 16 // 计算给定 nums[i] 所需的当前和 17 currentSum = requiredSum - nums[i]; 18 19 for (let j = i + 1; j < nums.length; j++) { 20 // 计算两个元素所需的三元组 21 tripleNeeded = currentSum - nums[j]; 22 23 // 检查所需的第三个元素是否存在于哈希表中 24 if (hashmap.has(tripleNeeded)) { 25 return true; 26 } 27 // 将当前元素添加到哈希表中 28 hashmap.add(nums[j]); 29 } 30 } 31 return false; 32}; 33 34 35let nums1 = [3, 7, 1, 2, 8, 4, 5]; 36let testList1 = [10, 20, 21]; 37 38console.log("1. 原始数组: " + printArray(nums1)); 39for (let test of testList1) { 40 if (findSumOfThree(nums1, test)) { 41 console.log(" 和为 " + test + " 的组合存在 "); 42 } else { 43 console.log(" 和为 " + test + " 的组合不存在 "); 44 } 45} 46console.log( 47 "------------------------------------------------------------------------------------------------------\n"); 48 49let nums2 = [-1, 2, 1, -4, 5, -3]; 50let testList2 = [-8, 0, 7]; 51 52console.log("2. 原始数组: " + printArray(nums2)); 53for (let test of testList2) { 54 if (findSumOfThree(nums2, test)) { 55 console.log(" 和为 " + test + " 的组合存在 "); 56 } else { 57 console.log(" 和为 " + test + " 的组合不存在 "); 58 } 59} 60console.log( 61 "------------------------------------------------------------------------------------------------------\n");
Ruby
1require 'set' 2 3def find_sum_of_three(nums, required_sum) 4 # 创建无序哈希表/集合 5 hashmap = Set.new 6 7 # 逐个固定一个元素，并寻找另外两个 8 for i in 0 .. nums.length - 2 9 # 清空哈希表以供每次迭代使用 10 hashmap.clear 11 12 # 计算给定 nums[i] 所需的当前和 13 current_sum = required_sum - nums[i] 14 15 for j in i + 1 .. nums.length - 1 16 # 计算两个元素所需的三元组 17 triple_needed = current_sum - nums[j] 18 19 # 检查所需的第三个元素是否存在于哈希表中 20 return true if hashmap.include?triple_needed 21 # 将当前元素添加到哈希表/集合中 22 hashmap.add(nums[j]) 23 end 24 end 25 return false 26end 27 28 29nums_lists = [[3, 7, 1, 2, 8, 4, 5], [-1, 2, 1, -4, 5, -3]] 30test_lists = [[10, 20, 21], [-8, 0, 7]] 31 32nums_lists.length.times do |i| 33 print (i + 1).to_s + ". 原始数组: " + nums_lists[i].to_s 34 test_lists[i].length.times do |j| 35 if find_sum_of_three(nums_lists[i], test_lists[i][j]) 36 print "\n 和为 " + test_lists[i][j].to_s + " 的组合存在" 37 else 38 print "\n 和为 "+ test_lists[i][j].to_s + " 的组合不存在" 39 end 40 end 41 print "\n------------------------------------------------------------------------------------------------------\n" 42end
Go
1package main 2import ( 3 "fmt" 4 "strconv" 5) 6 7// FindSumOfThree 是我们的挑战函数 8func FindSumOfThree(nums []int, RequiredSum int) bool { 9 // 创建两个变量来跟踪当前和 10 // 以及存储所需的三元组 11 currentSum, triplesNeeded := 0, 0 12 13 for i := 0; i < len(nums) - 1; i++ { 14 // 为每次迭代创建一个新的自定义无序哈希集 15 HashSet := NewSet() 16 17 // 计算给定 nums[i] 所需的当前和 18 currentSum = RequiredSum - nums[i] 19 20 // 逐个固定一个元素，并寻找另外两个 21 for j := i + 1; j < len(nums); j++ { 22 // 计算两个元素所需的三元组 23 triplesNeeded = currentSum - nums[j] 24 25 // 检查所需的第三个元素是否存在于哈希集中 26 if HashSet.Exists(triplesNeeded) { 27 return true 28 } 29 // 将当前元素添加到哈希集中 30 HashSet.Add(nums[j]) 31 } 32 } 33 return false 34} 35 36/* ArrayToString 用于将整数数组转换为字符串。 37ArrayToString 作为辅助函数在主函数中用于打印目的。 */ 38func ArrayToString(nums []int) string{ 39 if len(nums) == 0 { 40 return "[]" 41 } 42 res := "[" 43 for _, num := range nums { 44 res += strconv.Itoa(num) + ", " 45 } 46 res += "]" 47 return res[:len(res) - 3] + "]" 48} 49 50func main() { 51 numsLists := [][]int{{3, 7, 1, 2, 8, 4, 5}, {-1, 2, 1, -4, 5, -3}} 52 TestLists := [][]int{{10, 20, 21}, {-8, 0, 7}} 53 for i, nList := range numsLists { 54 fmt.Printf("%d. 原始数组: %s\n", i + 1, ArrayToString(nList)) 55 for _, tList := range TestLists[i] { 56 if FindSumOfThree(nList, tList) { 57 fmt.Printf(" 和为 %d 的组合存在\n", tList) 58 } else { 59 fmt.Printf(" 和为 %d 的组合不存在\n", tList) 60 } 61 } 62 fmt.Print("------------------------------------------------------------------------------------------------------\n") 63 } 64}
时间复杂度
此解法的时间复杂度为二次方级，。
空间复杂度
此解法的空间复杂度为线性级，。