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;
    }
}