18. 4Sum

Tags

1. Array
2. Hash Table
3. Two Pointer

Given an array S of n integers, are there elements a, b, c, and d in S 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.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
 A solution set is: 
[ 
  [-1, 0, 0, 1], 
  [-2, -1, 1, 2], 
  [-2, 0, 0, 2] 
]

题意：

给定一个含有n个整数的数组S，是否存在元素a, b, c, 和 d 在数组S中可以满足 a + b + c + d = target ？在给定目标值的和以后找到在数组S中所有不重复的元素组合。

分析：

本题跟题15，16相似，我们只需比较四个数相加的和与目标数字相等。然后返回所有的组合数组。所以，思路一样的是遍历每个数，对剩余数组进行双指针扫描。区别仅在于之前循环一层，本题循环两层。

思路：

1. 将数组升序排序
2. 如果数组中数字个数小于4返回空数组
3. 从0开始，两位外层双层循环，内层两层双指针左右扫描，如果四个数字相加等于目标值则放入临时数组返回，如果小于，则左移；大于，则右移。

Js实现：

复杂度

时间复杂度O(n³)

方法 #1

var fourSum = function(nums, target) {
 let res = [];
 nums.sort(function(a, b) {
   return a - b;
 });

 if (nums === null || nums.length < 4) return res;

 for (let i = 0; i < nums.length - 3; i++) {
 if (i !== 0 && nums[i] === nums[i - 1]) {
   continue;
 }
 for (let j = i + 1; j < nums.length - 2; j++) {
 if (j !== i + 1 && nums[j] === nums[j - 1]) {
   continue;
 }

 let left = j + 1;
 let right = nums.length - 1;

 while (left < right) {
 let sum = nums[i] + nums[j] + nums[left] + nums[right];
 if (sum < target) {
   left++;
 } else if (sum > target) {
   right--;
 } else {
   let tmp = [];
   tmp.push(nums[i]);
   tmp.push(nums[j]);
   tmp.push(nums[left]);
   tmp.push(nums[right]);
   res.push(tmp);
   left++;
   right--;
 while (left < right && nums[left] === nums[left - 1]) {
   left++;
 }
 while (left < right && nums[right] === nums[right + 1]) {
   right--;
         }
       }
     }
   }
 }
 return res;};

方法 #2

4 to 3 to 2

var fourSum = function(nums, target) { 
  let result = [];
  const len = nums.length; 
  if (nums === null || len < 4) return result;
  nums.sort(function(a, b) { return a - b; });

  let max = nums[len - 1]; 
  if (4 * nums[0] > target || 4 * max < target) return result;

  let i, z; 
  for (i = 0; i < len; i++) { 
    z = nums[i]; 
    if (i > 0 && z == nums[i - 1])  // avoid duplicate 
      continue; 
    if (z + 3 * max < target) // z is too small 
        continue; 
      if (4 * z > target) // z is too large 
          break; 
        if (4 * z == target) { // z is the boundary 
          if (i + 3 < len && nums[i + 3] == z) { 
            let inres = []; 
            inres.push(z); 
            inres.push(z); 
            inres.push(z); 
            inres.push(z); 
            result.push(inres);
            break; 
          }
       }

   threeSumForFourSum(nums, target - z, i + 1, len - 1, result, z); }

   return result;

};

function threeSumForFourSum(nums, target, low, high, fourSumList, z1) { 
  if (low + 1 >= high) return;

  let max = nums[high]; 
  if (3 * nums[low] > target || 3 * max < target) return;

  let i, z; 
  for (i = low; i < high - 1; i++) { 
    z = nums[i];
    if (i > low && z == nums[i - 1]) // avoid duplicate 
      continue; 
    if (z + 2 * max < target) // z is too small 
      continue;

     if (3 * z > target) // z is too large 
        break;

 if (3 * z == target) { // z is the boundary 
    if (i + 1 < high && nums[i + 2] == z) { 
      let infourSumList = []; 
      infourSumList.push(z1); 
      infourSumList.push(z); 
      infourSumList.push(z); 
      infourSumList.push(z); 
      fourSumList.push(infourSumList);
      break; 
    } 
  }

 twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z); 
  }
}

function twoSumForFourSum(nums, target, low, high, fourSumList, z1, z2) { 
  if (low >= high) return;

  if (2 * nums[low] > target || 2 * nums[high] < target) return;

  let i = low, j = high, sum, x; 
  while (i < j) { 
    sum = nums[i] + nums[j]; 
    if (sum == target) { 
      let infourSumList = []; 
      infourSumList.push(z1); 
      infourSumList.push(z2); 
      infourSumList.push(nums[i]); 
      infourSumList.push(nums[j]); 
      fourSumList.push(infourSumList);
      x = nums[i]; 
      while (++i < j && x == nums[i]) 
      ; 
      x = nums[j]; 
      while (i < --j && x == nums[j]) 
      ;
   } 
    if (sum < target) i++; 
    if (sum > target) j--;
   } 
  return;
}