如何使用java實現四數之和

如何使用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實現四數之和有所幫助。如果你有任何問題或建議，歡迎在評論區留言討論。