18. 4Sum

题意：

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

分析：

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

思路：

将数组升序排序
如果数组中数字个数小于4返回空数组
从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;};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

方法 #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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

# 18. 4Sum

# Tags

# 题意：

# 分析：

# 思路：

# Js实现：

# 复杂度

18. 4Sum

Tags

题意：

分析：

思路：

Js实现：

复杂度