18. 4Sum.md

18. 4Sum

Question:

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• The solution set must not contain duplicate quadruplets.

Thinking:

• Method: It is very similar to 3sum, but we use one more index to iterate. It is very important to remove duplicate elements.

	class Solution {
	    public List<List<Integer>> fourSum(int[] nums, int target) {
	        List<List<Integer>> result = new ArrayList<List<Integer>>();
	        if(nums == null || nums.length < 4) return result;
	        Arrays.sort(nums);
	        int len = nums.length;
	        for(int i = 0; i < len - 3; i++){
	            for(int j = i+1; j < len - 2; j++){
	                int left = j + 1; int right = len - 1;
	                while(left < right){
	                    int temp = nums[i] + nums[j] + nums[left] + nums[right];
	                    if(temp == target){
	                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
	                        left++;right--;
	                        while(left < right && nums[left-1] == nums[left])   left++;
	                        while(left < right && nums[right+1] == nums[right]) right--;
	                    }else if(temp < target){
	                        left++;
	                    }else{
	                        right--;
	                    }
	                }
	                while(j < len - 2 && nums[j + 1] == nums[j])  j++;//Remove duplicate.
	            }
	            while(i < len-3 && nums[i + 1] == nums[i])   i++;//Remove duplicate.
	        }
	        return result;
	    }
	}

二刷

1. 和一刷的时候类似，外围二次遍历，内部使用双指针。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length < 4) return result;
        int low = 0, high = 0, sum = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 3; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j < nums.length - 2; j++){
                if(j - i > 1 && nums[j - 1] == nums[j]) continue;
                low = j + 1; high = nums.length - 1;
                while(low < high){
                    sum = nums[i] + nums[j] + nums[low] + nums[high];
                    if(sum == target){
                        result.add(Arrays.asList(nums[i], nums[j], nums[low++], nums[high--]));
                        while(high > low && nums[high] == nums[high + 1]) high--;
                        while(low < high && nums[low] == nums[low - 1]) low++;
                    }else if(sum > target){
                        --high;
                    }else
                        ++low;
                }
            }
        }
        return result;
    }
}