题目描述（中等难度）

18. 4Sum - 图1

和3Sum类似，只不过是找四个数，使得和为 target，并且不能有重复的序列。

如果之前没有做过3Sum可以先看看，自己在上边的基础上加了一个循环而已。

  1. public List<List<Integer>> fourSum(int[] num, int target) {
  2.     Arrays.sort(num);
  3.     List<List<Integer>> res = new LinkedList<>();
  4.     //多加了层循环
  5.     for (int j = 0; j < num.length - 3; j++) {
  6.         //防止重复的
  7.         if (j == 0 || (j > 0 && num[j] != num[j - 1]))
  8.             for (int i = j + 1; i < num.length - 2; i++) {
  9.                 //防止重复的，不再是 i == 0 ，因为 i 从 j + 1 开始
  10.                 if (i == j + 1 || num[i] != num[i - 1]) {
  11.                     int lo = i + 1, hi = num.length - 1, sum = target - num[j] - num[i];
  12.                     while (lo < hi) {
  13.                         if (num[lo] + num[hi] == sum) {
  14.                             res.add(Arrays.asList(num[j], num[i], num[lo], num[hi]));
  15.                             while (lo < hi && num[lo] == num[lo + 1])
  16.                                 lo++;
  17.                             while (lo < hi && num[hi] == num[hi - 1])
  18.                                 hi--;
  19.                             lo++;
  20.                             hi--;
  21.                         } else if (num[lo] + num[hi] < sum)
  22.                             lo++;
  23.                         else
  24.                             hi--;
  25.                     }
  26.                 }
  27.             }
  28.     }
  29.     return res;
  30. }

时间复杂度：O（n³）。

空间复杂度：O（N），最坏情况，即 N 是指 n 个元素的排列组合个数，即

18. 4Sum - 图2

，用来保存结果。

总

完全是按照 3Sum 的思路写的，比较好理解。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情