三数之和

1. 问题描述

题目

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例

示例 1:
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2:
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3:
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

约束条件

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

2. 核心难点分析

主要挑战

1. 去重问题：如何避免重复的三元组
2. 效率优化：如何在O(n²)时间内解决
3. 边界处理：处理各种特殊情况
4. 算法选择：选择最优的解法策略

关键洞察

• 排序后使用双指针可以有效降低时间复杂度
• 通过跳过重复元素来避免重复解
• 利用数组有序性进行剪枝优化

3. 解法分析

解法一：暴力解法（不推荐）

思路：三重循环遍历所有可能的三元组组合

时间复杂度：O(n³) 空间复杂度：O(1)

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Set<List<Integer>> set = new HashSet<>();
    
    for (int i = 0; i < nums.length - 2; i++) {
        for (int j = i + 1; j < nums.length - 1; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                    Collections.sort(triplet);
                    set.add(triplet);
                }
            }
        }
    }
    
    result.addAll(set);
    return result;
}

解法二：排序 + 双指针（推荐）

思路：

1. 先对数组进行排序
2. 固定第一个数，用双指针在剩余数组中寻找另外两个数
3. 通过移动指针和跳过重复元素来避免重复解

时间复杂度：O(n²) 空间复杂度：O(1)

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    
    // 边界检查
    if (nums == null || nums.length < 3) {
        return result;
    }
    
    // 排序
    Arrays.sort(nums);
    
    for (int i = 0; i < nums.length - 2; i++) {
        // 跳过重复的第一个数
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        
        // 剪枝优化：如果最小的三个数之和都大于0，后面不可能有解
        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
            break;
        }
        
        // 剪枝优化：如果当前数与最大的两个数之和都小于0，当前数太小
        if (nums[i] + nums[nums.length - 2] + nums[nums.length - 1] < 0) {
            continue;
        }
        
        int left = i + 1;
        int right = nums.length - 1;
        
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                // 跳过重复的left
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                // 跳过重复的right
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

解法三：哈希表优化

思路：固定两个数，用哈希表查找第三个数

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Set<List<Integer>> set = new HashSet<>();
    
    Arrays.sort(nums);
    
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        Set<Integer> seen = new HashSet<>();
        for (int j = i + 1; j < nums.length; j++) {
            int target = -(nums[i] + nums[j]);
            
            if (seen.contains(target)) {
                List<Integer> triplet = Arrays.asList(nums[i], target, nums[j]);
                Collections.sort(triplet);
                set.add(triplet);
            }
            seen.add(nums[j]);
        }
    }
    
    result.addAll(set);
    return result;
}

4. Python实现

def threeSum(nums):
    """
    三数之和 - 双指针解法
    """
    result = []
    
    # 边界检查
    if not nums or len(nums) < 3:
        return result
    
    # 排序
    nums.sort()
    
    for i in range(len(nums) - 2):
        # 跳过重复的第一个数
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # 剪枝优化
        if nums[i] + nums[i + 1] + nums[i + 2] > 0:
            break
        
        if nums[i] + nums[-2] + nums[-1] < 0:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum == 0:
                result.append([nums[i], nums[left], nums[right]])
                
                # 跳过重复元素
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif current_sum < 0:
                left += 1
            else:
                right -= 1
    
    return result

# 测试用例
def test_threeSum():
    # 测试用例1
    nums1 = [-1, 0, 1, 2, -1, -4]
    print(f"输入: {nums1}")
    print(f"输出: {threeSum(nums1)}")
    
    # 测试用例2
    nums2 = [0, 1, 1]
    print(f"输入: {nums2}")
    print(f"输出: {threeSum(nums2)}")
    
    # 测试用例3
    nums3 = [0, 0, 0]
    print(f"输入: {nums3}")
    print(f"输出: {threeSum(nums3)}")

if __name__ == "__main__":
    test_threeSum()

5. 复杂度分析

时间复杂度对比

解法	时间复杂度	空间复杂度	优缺点
暴力解法	O(n³)	O(1)	简单但效率低
双指针	O(n²)	O(1)	最优解，推荐使用
哈希表	O(n²)	O(n)	空间换时间，去重复杂

详细分析

双指针解法：

• 时间复杂度：O(n²)

  • 排序：O(n log n)
  • 外层循环：O(n)
  • 内层双指针：O(n)
  • 总体：O(n log n) + O(n²) = O(n²)

• 空间复杂度：O(1)

  • 不考虑结果存储的额外空间
  • 只使用了常数个变量

6. 边界情况处理

常见边界情况

public List<List<Integer>> threeSumWithBoundaryCheck(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    
    // 1. 空数组或长度不足
    if (nums == null || nums.length < 3) {
        return result;
    }
    
    Arrays.sort(nums);
    
    // 2. 所有数都为正数
    if (nums[0] > 0) {
        return result;
    }
    
    // 3. 所有数都为负数
    if (nums[nums.length - 1] < 0) {
        return result;
    }
    
    // 4. 数组长度刚好为3
    if (nums.length == 3) {
        if (nums[0] + nums[1] + nums[2] == 0) {
            result.add(Arrays.asList(nums[0], nums[1], nums[2]));
        }
        return result;
    }
    
    // 正常处理逻辑...
    return result;
}

测试用例设计

@Test
public void testBoundaryCases() {
    // 边界情况1：空数组
    assertThat(threeSum(new int[]{})).isEmpty();
    
    // 边界情况2：长度不足
    assertThat(threeSum(new int[]{1, 2})).isEmpty();
    
    // 边界情况3：无解情况
    assertThat(threeSum(new int[]{1, 2, 3})).isEmpty();
    
    // 边界情况4：全零
    assertThat(threeSum(new int[]{0, 0, 0})).containsExactly(Arrays.asList(0, 0, 0));
    
    // 边界情况5：重复元素多
    assertThat(threeSum(new int[]{-1, -1, -1, 0, 1, 1, 1})).hasSize(2);
}

7. 相关变种问题

7.1 两数之和 (Two Sum)

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    
    return new int[]{};
}

7.2 四数之和 (Four Sum)

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (nums == null || nums.length < 4) {
        return result;
    }
    
    Arrays.sort(nums);
    
    for (int i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        for (int j = i + 1; j < nums.length - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            
            int left = j + 1, right = nums.length - 1;
            
            while (left < right) {
                long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                
                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    
    return result;
}

7.3 最接近的三数之和

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int closest = nums[0] + nums[1] + nums[2];
    
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1, right = nums.length - 1;
        
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            
            if (Math.abs(sum - target) < Math.abs(closest - target)) {
                closest = sum;
            }
            
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return closest;
}

8. 性能优化技巧

8.1 剪枝优化

public List<List<Integer>> threeSumOptimized(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        // 剪枝1：最小三数和大于0
        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
        
        // 剪枝2：最大三数和小于0
        if (nums[i] + nums[nums.length - 2] + nums[nums.length - 1] < 0) continue;
        
        int left = i + 1, right = nums.length - 1;
        
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                // 批量跳过重复元素
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

8.2 内存优化

public List<List<Integer>> threeSumMemoryOptimized(int[] nums) {
    // 预估结果大小，减少扩容
    List<List<Integer>> result = new ArrayList<>(nums.length / 3);
    
    Arrays.sort(nums);
    
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1, right = nums.length - 1;
        
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            
            if (sum == 0) {
                // 直接创建不可变列表，节省内存
                result.add(List.of(nums[i], nums[left], nums[right]));
                
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

9. 实际应用场景

9.1 金融风控系统

/**
 * 在金融风控中寻找可疑的资金流向组合
 */
public class RiskDetection {
    public List<List<Transaction>> findSuspiciousTransactions(
            List<Transaction> transactions, double targetAmount) {
        
        List<List<Transaction>> suspicious = new ArrayList<>();
        
        // 按金额排序
        transactions.sort(Comparator.comparing(Transaction::getAmount));
        
        for (int i = 0; i < transactions.size() - 2; i++) {
            if (i > 0 && transactions.get(i).getAmount().equals(
                    transactions.get(i - 1).getAmount())) {
                continue;
            }
            
            int left = i + 1, right = transactions.size() - 1;
            
            while (left < right) {
                double sum = transactions.get(i).getAmount() + 
                           transactions.get(left).getAmount() + 
                           transactions.get(right).getAmount();
                
                if (Math.abs(sum - targetAmount) < 0.01) { // 容差范围
                    suspicious.add(Arrays.asList(
                        transactions.get(i),
                        transactions.get(left),
                        transactions.get(right)
                    ));
                    
                    left++;
                    right--;
                } else if (sum < targetAmount) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return suspicious;
    }
}

9.2 推荐系统

/**
 * 在推荐系统中寻找用户兴趣的最佳组合
 */
public class RecommendationEngine {
    public List<List<Item>> findOptimalCombinations(
            List<Item> items, double targetScore) {
        
        List<List<Item>> combinations = new ArrayList<>();
        
        // 按评分排序
        items.sort(Comparator.comparing(Item::getScore));
        
        for (int i = 0; i < items.size() - 2; i++) {
            int left = i + 1, right = items.size() - 1;
            
            while (left < right) {
                double totalScore = items.get(i).getScore() + 
                                  items.get(left).getScore() + 
                                  items.get(right).getScore();
                
                if (Math.abs(totalScore - targetScore) < 0.1) {
                    combinations.add(Arrays.asList(
                        items.get(i),
                        items.get(left),
                        items.get(right)
                    ));
                }
                
                if (totalScore < targetScore) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return combinations;
    }
}

10. 常见错误与调试

10.1 常见错误

错误1：忘记去重

// 错误示例
for (int i = 0; i < nums.length - 2; i++) {
    // 缺少去重逻辑
    int left = i + 1, right = nums.length - 1;
    // ...
}

// 正确示例
for (int i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
    int left = i + 1, right = nums.length - 1;
    // ...
}

错误2：边界条件处理不当

// 错误示例
while (left < right && nums[left] == nums[left + 1]) {
    left++; // 可能越界
}

// 正确示例
while (left < right && nums[left] == nums[left + 1]) {
    left++;
}
while (left < right && nums[right] == nums[right - 1]) {
    right--;
}

10.2 调试技巧

public List<List<Integer>> threeSumWithDebug(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    
    System.out.println("原数组: " + Arrays.toString(nums));
    Arrays.sort(nums);
    System.out.println("排序后: " + Arrays.toString(nums));
    
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            System.out.println("跳过重复元素: " + nums[i]);
            continue;
        }
        
        System.out.println("固定第一个数: " + nums[i]);
        
        int left = i + 1, right = nums.length - 1;
        
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            System.out.printf("尝试组合: [%d, %d, %d], 和: %d%n", 
                            nums[i], nums[left], nums[right], sum);
            
            if (sum == 0) {
                List<Integer> triplet = Arrays.asList(nums[i], nums[left], nums[right]);
                result.add(triplet);
                System.out.println("找到解: " + triplet);
                
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

11. 面试要点总结

11.1 关键考点

1. 算法选择：能否想到排序+双指针的最优解
2. 去重处理：如何正确处理重复元素
3. 边界条件：各种特殊情况的处理
4. 代码实现：指针移动和循环控制的正确性
5. 优化思路：剪枝等性能优化技巧

11.2 面试回答模板

第一步：理解题意

• "这道题要求找出所有和为0的不重复三元组"
• "关键难点是去重和效率优化"

第二步：分析解法

• "我考虑用排序+双指针的方法"
• "时间复杂度可以优化到O(n²)"

第三步：实现细节

• "首先排序，然后固定第一个数"
• "用双指针在剩余数组中寻找另外两个数"
• "通过跳过重复元素来去重"

第四步：复杂度分析

• "时间复杂度O(n²)，空间复杂度O(1)"

第五步：测试验证

• "考虑边界情况：空数组、无解、全零等"

11.3 进阶问题

面试官可能的追问：

1. "如何扩展到四数之和？"
2. "如果要求找最接近target的三数之和怎么办？"
3. "能否用其他方法解决？"
4. "如何进一步优化性能？"

12. 总结

核心要点

1. 排序+双指针是解决三数之和问题的最优方法
2. 去重逻辑是实现正确性的关键
3. 剪枝优化可以显著提升性能
4. 边界条件处理确保代码的健壮性

学习建议

1. 掌握双指针技巧：这是解决多数之和问题的通用方法
2. 理解去重原理：排序后跳过重复元素的策略
3. 练习变种问题：两数之和、四数之和等
4. 关注性能优化：剪枝、内存优化等技巧
5. 重视测试验证：全面的测试用例设计

扩展学习

• 学习更多双指针应用场景
• 研究哈希表在组合问题中的应用
• 了解回溯算法在N数之和中的应用
• 掌握滑动窗口等相关技巧

通过深入理解三数之和问题，可以为解决更复杂的组合优化问题打下坚实基础。