2. 3Sum 4Sum

---

https://leetcode.com/problems/3sum/submissions/731187734/

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
 
        for(int i=0;i<n;i++){
            if(i > 0 && nums[i] == nums[i-1]) continue;  // for unique i [1,2,2,2,2,3,4] // use 2 element once
 
            int target = -1 * nums[i];
            int s = i + 1;
            int e = n - 1;
            while(s<e){
                int sum = nums[s] + nums[e];
 
                if (sum > target){
                    e--;
                } else if (sum < target){
                    s++;
                } else {
                    ans.push_back({nums[i], nums[s], nums[e]});
                    s++;
                    e--;
                    while(s <e && nums[s] == nums[s-1]) s++; // [0,0,0,0] // unique s
                    while(s <e && nums[e] == nums[e+1]) e--; // [0,0,0,0] // unique e
                }
            }
        }
        return ans;
    }
};

4Sum

 
// 1 1 1 2 2 2 3 3 3 4 4 4 5 5 
// target = 8 
 
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
 
        int n = nums.size();
        vector<vector<int>> ans;
 
        for(int i=0;i<n;i++){
            if(i>0 and nums[i]==nums[i-1]) continue;
            for(int j = i+1; j < n; j++){
                if(j!=i+1 and nums[j]==nums[j-1]) continue; // imp j!=i+1
 
                int s = j+1, e = n-1;
                while(s < e)
                {
                    long long totalSum = (long long)nums[i] + (long long)nums[j] + (long long)nums[s] + (long long)nums[e];
 
                    if (totalSum > target) {
                        e--;
                    } else if (totalSum < target) {
                        s++;
                    } else {
                        ans.push_back({nums[i], nums[j], nums[s], nums[e]});
                        e--;
                        s++;
                        while(s<e && nums[s] == nums[s-1]) s++; // missed = s-1 made it s+1
                        while(s<e && nums[e] == nums[e+1]) e--; // 
                    }
                }
            }
        }
 
        return ans;
    }
};
 
 
 

---