判定数组中是否存在和为给定值X的三元组算法问题

问题描述 #

给定大小为n的数组arr以及整数X，判断数组中是否存在三个元素，其元素之和等于给定整数X。

输入输出示例 #

输入：
n = 5, X = 10
arr[] = [1, 2, 4, 3, 6]

输出：
Yes

解释说明：数组中的三元组{1, 3, 6}的元素之和为10，满足题目要求。

解法1：排序+双指针法（推荐，空间复杂度更低） #

这是最常用的解法，时间复杂度为O(n²)，空间复杂度为O(1)（不计排序占用的栈空间），实现思路如下：

• 先将数组按升序排序
• 遍历数组固定第一个元素arr[i]，将问题转化为：在i下标之后的子数组中，寻找两个元素之和等于X - arr[i]
• 初始化左右指针分别指向子数组的首尾，计算两数之和：
  • 若和等于目标值，直接返回存在符合要求的三元组
  • 若和小于目标值，左指针右移增大当前总和
  • 若和大于目标值，右指针左移减小当前总和
• 遍历完所有可选的第一个元素仍未找到匹配三元组，返回不存在

参考代码（Python）：

def check_triplet_sum(arr, n, target_sum):
    arr.sort()
    for i in range(n - 2):
        left = i + 1
        right = n - 1
        current_target = target_sum - arr[i]
        while left < right:
            two_sum = arr[left] + arr[right]
            if two_sum == current_target:
                return True
            elif two_sum < current_target:
                left += 1
            else:
                right -= 1
    return False

# 测试示例
arr = [1,2,4,3,6]
n = 5
X = 10
print("Yes" if check_triplet_sum(arr, n, X) else "No")

解法2：哈希表法（无需修改原数组） #

如果不允许修改原数组，可以选择该方法，时间复杂度为O(n²)，空间复杂度为O(n)，实现思路如下：

• 遍历数组固定第一个元素arr[i]，将问题转化为：在i下标之后的子数组中，寻找两个元素之和等于X - arr[i]
• 初始化空哈希表存储已经遍历过的第二个元素，逐个遍历后续元素arr[j]
• 若(X - arr[i] - arr[j])存在于哈希表中，说明找到符合要求的三元组，直接返回True；否则将arr[j]存入哈希表
• 遍历完所有可能仍未找到，返回不存在

内容的提问来源于stack exchange，提问作者Vinay Edula