题目描述（中等难度）

和3Sum类似，只不过是找四个数，使得和为 target，并且不能有重复的序列。 如果之前没有做过3Sum可以先看看，自己在上边的基础上加了一个循环而已。 1. public List> fourSum(int[] num, int target) { 2. Arrays.sort(num); 3. List> 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 个元素的排列组合个数，即 ，用来保存结果。

总

完全是按照 3Sum 的思路写的，比较好理解。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情