题目出处
18-四数之和-题目出处
题目描述
个人解法
思路：
todo
代码示例：（Java）
todo
复杂度分析
todo
官方解法
18-四数之和-官方解法
方法1：排序+双指针
思路：
代码示例：（Java）
public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();if (nums == null || nums.length < 4) {return quadruplets;}Arrays.sort(nums);int length = nums.length;for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
复杂度分析
考察知识点
收获
Gitee源码位置
18-四数之和-源代码
同名文章，已同步发表于CSDN，个人网站，公众号
- CSDN
工一木子 - 个人网站
工藤新一 - 公众号
