LeetCode 4Sum：排序雙指針 O(n^3) 優化去重

問題描述

給定數組 num 和目標值 target，找出所有不重複的四元組 [a,b,c,d] 使和為 target。四元組內非遞減，結果不重複。

排序 + 兩層循環 + 雙指針

1. 排序數組。
2. 第一層 i 遍歷第一個數，去重：i>0 && num[i]==num[i-1] continue。
3. 第二層 j 遍歷第二個數（j>i），同樣去重。
4. 雙指針 l=j+1, r=n-1 尋找第三、四個數。sum = num[i]+num[j]+num[l]+num[r]。
   • sum == target：加入答案，l++ 跳過重複，r-- 跳過重複。
   • sum < target：l++ 跳過重複。
   • sum > target：r-- 跳過重複。

代碼

vector> fourSum(vector& num, int target) {
    vector> res;
    int n = num.size(); if(n<4) return res;
    sort(num.begin(), num.end());
    for(int i=0;i0 && num[i]==num[i-1]) continue;
        for(int j=i+1;ji+1 && num[j]==num[j-1]) continue;
            int l=j+1, r=n-1;
            while(l