如何使用Java实现四数之和

引言

在算法问题中，”四数之和”（4Sum）是一个经典的问题。它要求在一个数组中找出所有满足四个数之和等于目标值的组合。这个问题是”三数之和”（3Sum）问题的扩展，通常用于考察对数组处理、双指针技巧以及去重等算法的掌握程度。本文将详细介绍如何使用Java实现四数之和的算法。

问题描述

给定一个包含n个整数的数组nums和一个目标值target，找出所有满足a + b + c + d = target的四元组(a, b, c, d)。要求四元组中的元素不能重复，且每个元素只能使用一次。

解决思路

1. 暴力解法

最直观的解法是使用四重循环遍历所有可能的四元组，检查它们的和是否等于目标值。这种解法的时间复杂度为O(n^4)，在数组较大时效率极低，因此不推荐使用。

2. 排序 + 双指针

为了提高效率，我们可以采用排序加双指针的方法。具体步骤如下：

1. 排序：首先对数组进行排序，这样可以利用有序性来减少不必要的计算。
2. 双重循环：使用两重循环固定前两个数nums[i]和nums[j]。
3. 双指针：在剩下的数组中使用双指针left和right来寻找满足nums[i] + nums[j] + nums[left] + nums[right] = target的组合。
4. 去重：为了避免重复的四元组，需要在每一步中跳过重复的元素。

代码实现

以下是使用Java实现四数之和的代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FourSum {
    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);
        int n = nums.length;
        
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 跳过重复的元素
            }
            
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue; // 跳过重复的元素
                }
                
                int left = j + 1;
                int right = n - 1;
                
                while (left < right) {
                    int sum = 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;
    }

    public static void main(String[] args) {
        FourSum solution = new FourSum();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> result = solution.fourSum(nums, target);
        
        for (List<Integer> list : result) {
            System.out.println(list);
        }
    }
}

代码解析

1. 排序：首先对数组进行排序，这样可以利用有序性来减少不必要的计算。
2. 双重循环：外层循环固定第一个数nums[i]，内层循环固定第二个数nums[j]。
3. 双指针：在剩下的数组中使用双指针left和right来寻找满足条件的组合。
4. 去重：在每一步中跳过重复的元素，以避免生成重复的四元组。

时间复杂度分析

• 排序：O(n log n)
• 双重循环：O(n^2)
• 双指针：O(n)

因此，总的时间复杂度为O(n^3)，比暴力解法的O(n^4)要高效得多。

结论

通过排序和双指针的技巧，我们可以有效地解决四数之和的问题。这种方法不仅提高了算法的效率，还避免了重复的四元组。在实际应用中，这种技巧可以推广到更多类似的求和问题中。

希望本文对你理解如何使用Java实现四数之和有所帮助。如果你有任何问题或建议，欢迎在评论区留言讨论。