豆包MarsCode算法题：三数之和问题

问题描述

思路分析

1. 排序数组

• 目的: 将数组 arr 按升序排序，这样可以方便地使用双指针找到满足条件的三元组，同时避免重复的三元组被重复计算。
• 优势:
  • 数组有序后，处理两个数和 target - arr[i] 的问题可以通过双指针快速找到所有可能的组合。

2. 使用双指针寻找目标对

• 核心思路:
  • 对于每个固定的元素 a = arr[i] ，寻找剩下的两个元素 b , c 使得 a + b + c = target ，即 b + c = target - a 。
  • 设 left 和 right 分别指向当前子数组的起点和终点（i + 1 和 arr.length - 1），通过比较 arr[left] + arr[right] 和 target - arr[i] 的大小调整指针：
    • 如果 arr[left] + arr[right] < target - arr[i] ，说明需要更大的数，移动 left。
    • 如果 arr[left] + arr[right] > target - arr[i] ，说明需要更小的数，移动 right。
    • 如果两者相等，记录满足条件的对，并继续移动指针。

3. 处理重复元素

在满足条件时，需要仔细处理 arr[left] 和 arr[right] 的重复计数：

• 情况1: 如果 arr[left] != arr[right]：
  • 统计所有重复的 arr[left] 和 arr[right] 的数量，假设重复次数分别为 countLeft 和 countRight，则可以形成的三元组数为 countLeft × countRight 。
• 情况2: 如果 arr[left] == arr[right]：
  • 说明所有元素都相等，假设重复次数为 n，则可以形成的三元组数为：

• n 表示元素的重复次数。
• (n−1) 是从剩余元素中选择的方式数。

4. 结果取模

由于结果可能非常大，每次更新结果时都需要对 10⁹ + 7 取模，避免溢出。

算法复杂度

• 时间复杂度:时间复杂度为 O(n²) 。
• 空间复杂度: 只使用了常数级的额外空间，复杂度为 O(1) 。

参考代码（Java）

import java.util.Arrays;

public class Main {
    public static int solution(int[] arr, int t) {
        int MOD = 1_000_000_007;
        
        Arrays.sort(arr); // 排序
        int n = arr.length;
        long count = 0;

        for (int i = 0; i < n - 2; i++) {
            int target = t - arr[i];
            int left = i + 1, right = n - 1;

            while (left < right) {
                if (arr[left] + arr[right] == target) {
                    if (arr[left] == arr[right]) { // 如果左指针和右指针值相同
                        int num = right - left + 1;
                        count += (long) num * (num - 1) / 2; // 组合数C(num, 2)
                        count %= MOD;
                        break;
                    } else { // 如果左指针和右指针值不同
                        int leftCount = 1, rightCount = 1;

                        // 统计左指针相同值的个数
                        while (left + 1 < right && arr[left] == arr[left + 1]) {
                            left++;
                            leftCount++;
                        }

                        // 统计右指针相同值的个数
                        while (right - 1 > left && arr[right] == arr[right - 1]) {
                            right--;
                            rightCount++;
                        }

                        // 累加计数
                        count += (long) leftCount * rightCount;
                        count %= MOD;

                        left++;
                        right--;
                    }
                } else if (arr[left] + arr[right] < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return (int) count;
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[]{1, 1, 2, 2, 3, 3, 4, 4, 5, 5}, 8) == 20);
        System.out.println(solution(new int[]{2, 2, 2, 2}, 6) == 4);
        System.out.println(solution(new int[]{1, 2, 3, 4, 5}, 9) == 2);
        System.out.println(solution(new int[]{1, 1, 1, 1}, 3) == 4);
    }
}

代码分析

1. 排序和初始化

Arrays.sort(arr); // 排序
int n = arr.length;
long count = 0;

• 作用:
  • 对数组进行升序排序，使双指针查找两个数的和时能够利用有序性快速调整指针。
  • 初始化 count 用于累计满足条件的三元组数量。

2. 遍历数组

for (int i = 0; i < n - 2; i++) {
    int target = t - arr[i];
    int left = i + 1, right = n - 1;
}

• 作用:
  • 遍历数组的每个元素 arr[i]，将其固定为三元组的第一个数 a 。
  • 计算剩下两个数的目标和 target = t - arr[i]。
  • 设置双指针，left 从 i + 1 开始，right 从数组末尾开始。
• 边界条件:
  • 由于需要三个不同的数，循环只需要到 n - 2。
  • 避免越界错误。

3. 双指针查找两数之和

while (left < right) {
    if (arr[left] + arr[right] == target) {
        ...
    } else if (arr[left] + arr[right] < target) {
        left++;
    } else {
        right--;
    }
}

• 核心逻辑:
  • 当 arr[left] + arr[right] == target :
    • 找到一组满足条件的对，需要进一步统计并更新结果。
  • 当 arr[left] + arr[right] < target :
    • 总和太小，增加 left 指针以尝试增大总和。
  • 当 arr[left] + arr[right] > target :
    • 总和太大，减小 right 指针以尝试减小总和。

4. 处理双指针值相同的情况

if (arr[left] == arr[right]) { // 左右值相同
    int num = right - left + 1;
    count += (long) num * (num - 1) / 2; // 组合数C(num, 2)
    count %= MOD;
    break;
}

• 逻辑:
  • 如果 arr[left] == arr[right]，说明所有元素都相等，从中选择两个的组合数为 C(num, 2) = num × (num - 1) / 2 。
  • 直接更新 count，退出当前循环。

5. 处理双指针值不同的情况

int leftCount = 1, rightCount = 1;

// 统计左指针相同值的个数
while (left + 1 < right && arr[left] == arr[left + 1]) {
    left++;
    leftCount++;
}

// 统计右指针相同值的个数
while (right - 1 > left && arr[right] == arr[right - 1]) {
    right--;
    rightCount++;
}

// 累加计数
count += (long) leftCount * rightCount;
count %= MOD;

left++;
right--;

• 逻辑:
  • 统计重复值:
    • 使用两个循环分别统计 arr[left] 和 arr[right] 的重复次数。
  • 组合方式:
    • 如果 arr[left] 和 arr[right] 值不同，则可以形成 leftCount × rightCount 对满足条件的组合。
  • 更新 count 并对结果取模，防止溢出。

6. 结果返回

return (int) count;

• 将结果转换为 int 并返回，确保符合题目要求。