Leetcode-Solutions/scripts/algorithms/0-9/4Sum/4Sum.cpp at main · shvm83/Leetcode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        int n = nums.size();

        vector<vector<int> > answer;

        if(n<4) return answer;

        sort(nums.begin(),nums.end());

        for(int i=0;i<n;){
            for(int j=i+1;j<n;){

                int left = j+1;
                int right = n-1;

                long long int x = (long long int)target - (long long int)nums[i] - (long long int)nums[j];

                while(left<right){

                    if(x == nums[left]+nums[right]){
                    vector<int> vect{nums[i] , nums[j] , nums[left] , nums[right]};
                    answer.push_back(vect);

                    //skipping duplicates while moving right
                    int k = 1;
                    while((left+k)<n && nums[left+k]==nums[left]) ++k;

                    if((left+k)>=n) break;
                    else left = left+k;

                    //skipping duplicates while moving left
                    k = 1;
                    while((right-k)>=0 && nums[right-k]==nums[right]) ++k;

                    if((right-k)<0) break;
                    else right = right-k;

                }
                else{

                    if(x>nums[left]+nums[right]){

                        //skipping duplicates while moving right
                        int k = 1;
                        while((left+k)<n && nums[left+k]==nums[left]) ++k;

                        if((left+k)>=n) break;
                        else left = left+k;

                    }
                    else{

                        //skipping duplicates while moving left
                        int k = 1;
                        while((right-k)>=0 && nums[right-k]==nums[right]) ++k;

                        if((right-k)<0) break;
                        else right = right-k;

                    }

                }

                }

               //skipping duplicates while moving right
               int k = 1;
                while((j+k)<n && nums[j+k]==nums[j]) ++k;

                if((j+k)>=n) break;
                else j = j+k;

            }

            //skipping duplicates while moving right
            int k = 1;
            while((i+k)<n && nums[i+k]==nums[i]) ++k;

            if((i+k)>=n) break;
            else i = i+k;
        }

        return answer;
    }
};