Java O(n^3) solution


  • 0
    M

    The idea is similar with 3sum. You can get inspiration from 3sum.
    3sum: https://discuss.leetcode.com/topic/69698/java-o-n-2-solution

        // Assume no integer overflow
        public List<List<Integer>> fourSum(int[] nums, int target) {
            if(nums==null)  return null;
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            for(int a=0; a<nums.length-3; a++){
                if(a==0 || nums[a]!=nums[a-1]){
                    int sum1 = target-nums[a];
                    for(int b=a+1; b<nums.length-2; b++){
                        if(b==a+1 || nums[b]!=nums[b-1]){
                            int c = b+1, d=nums.length-1;
                            int sum2 = sum1-nums[b];
                        	while(c<d){
    	                        int add = nums[c]+nums[d];
    	                        if(add<sum2){
    	                            while(c<d && nums[c]==nums[c+1]) c++;
    	                            c++;
    	                        } else if(add>sum2){
    	                            while(c<d && nums[d]==nums[d-1]) d--;
    	                            d--;
    	                        } else {
    	                            res.add(Arrays.asList(nums[a],nums[b],nums[c],nums[d]));
    	                            while(c<d && nums[c]==nums[c+1]) c++;
    	                            while(c<d && nums[d]==nums[d-1]) d--;
    	                            c++;
    	                            d--;
    	                        }
                        	}
                        }
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.