今天第18題

題目

題目翻譯

給定一陣列和目標值(target)，回傳陣列中所有取四數相加為target的可能，且不能包含重複的可能

解題步驟

1. 問題描述：

   • 給定一個整數數組 nums 和一個目標值 target，需要找出數組中的四個數，使得它們的和等於 target，並返回所有不重複的四元組。

2. 四個數求和的基本思路：

   • 先將數組排序，這樣可以利用雙指針技術來優化查找過程。
   • 固定前兩個數，然後使用雙指針來處理剩下的兩個數，使它們的和與前兩個數加起來等於目標值 target。
   • 通過跳過重複數值來避免結果中包含重複的四元組。

3. 步驟分解：

   • 排序數組：首先將 nums 排序，這樣在後續查找過程中可以方便地使用雙指針技術。
   • 雙層循環固定前兩個數：使用兩個嵌套循環來固定前兩個數，並確保跳過重複的數值。
   • 雙指針處理後兩個數：對於剩下的兩個數，使用雙指針技術（從兩端向中間掃描），如果和小於 target 則移動左指針；如果和大於 target 則移動右指針。
   • 去重處理：使用 set 來存儲四元組，避免重複的組合出現。

4. 邊界處理：

   • 如果數組長度不足四個數，則直接返回空結果。

code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        
        if (n < 4) return res;  // 若數組長度小於 4，直接返回空結果
        
        sort(nums.begin(), nums.end());  // 將數組排序
        
        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, right = n - 1;
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum == target) {
                        res.push_back({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 res;
    }
};