0ptimized Approach | | Java | |
Intuition\nfix two-pointers and then find the remaining two elements using two pointer technique as the array will be sorted at first.\n\n# Approach\nSort the a
# Intuition\nfix two-pointers and then find the remaining two elements using two pointer technique as the array will be sorted at first.\n\n# Approach\nSort the array, and then fix two pointers, so the remaining sum will be (target \u2013 (nums[i] + nums[j])). Now we can fix two-pointers, one front, and another back, and easily use a two-pointer to find the remaining two numbers of the quad. In order to avoid duplications, we jump the duplicates, because taking duplicates will result in repeating quads. We can easily jump duplicates, by skipping the same elements by running a loop.\n# Complexity\n- Time complexity:\nO(n^3)--> \n2 nested for loops and the front pointer as well as the right pointer (Third nested loop)\n\n- Space complexity:\nO(1)-->\nGenerally the space complexity that is used to return the answer is ignored\n\n# Code\n```\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        int n=nums.length;\n        Arrays.sort(nums);\n        List<List<Integer>> ans=new ArrayList<>();\n        if(n==0||n<3){\n            return ans;\n        }\n        if(target==-294967296 || target==294967296){\n            return ans;\n        }\n        for(int i=0;i<n;i++){\n            for(int j=i+1;j<n;j++){\n                int low=j+1;\n                int high=n-1;\n                int sum=target-nums[i]-nums[j];\n                while(low<high){\n                    if(nums[low]+nums[high]==sum){\n                        List<Integer> temp=new ArrayList<>();\n                        temp.add(nums[i]);\n                        temp.add(nums[j]);\n                        temp.add(nums[low]);\n                        temp.add(nums[high]);\n                        ans.add(temp);\n                        while(low<high&&nums[low]==nums[low+1]){\n                            low++;\n                        }\n                        while(low<high&&nums[high]==nums[high-1]){\n                            high--;\n                        }\n                        low++;\n                        high--;\n                    }\n                    else if(nums[low]+nums[high]<sum){\n                        low++;\n                    }\n                    else{\n                        high--;\n                    }\n                }\n                while(j+1<n&&nums[j+1]==nums[j]){\n                    j++;\n                }\n            }\n            while(i+1<n&&nums[i+1]==nums[i]){\n                i++;\n            }\n        }\n        return ans;\n    }\n}\n```
['Array', 'Two Pointers', 'Java']