【每日一题Day266】LC18四数之和 | 排序+双指针

四数之和【LC18】

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）： 0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案 。

排序+双指针

思路 类似三数之和，先将数组排序，然后固定两个数 n u m s [ a ] , n u m s [ b ] nums[a],nums[b] nums[a],nums[b]，然后在区间 [ b + 1 , n − 1 ] [b+1,n-1] [b+1,n−1]使用双指针搜索是否有两数之和为 t a r g e t − n u m s [ a ] − n u m s [ b ] target-nums[a]-nums[b] target−nums[a]−nums[b]，如果有则记录答案；否则根据大小，右移左指针或者左移右指针。 注意去重以及溢出 优化： 判断最小四元组是否大于target，是则break 判断最大四元组是否小于target，实则continue 实现 class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for (int i = 0; i < n - 3; i++){ if (i > 0 && nums[i] == nums[i - 1]) continue; long x = nums[i]; if (x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; if (x + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue; for (int j = i + 1; j < n - 2; j++){ if (j > i + 1 && nums[j] == nums[j - 1]) continue; long sum2 = nums[i] + nums[j]; int l = j + 1, r = n - 1; long num = target - sum2; while (l < r){ if (nums[l] + nums[r] == num){ res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r])); l++; while (l < n && nums[l - 1] == nums[l]){ l++; } r--; while (r > l && nums[r + 1] == nums[r]){ r--; } }else if (nums[l] + nums[r] > num){ r--; }else{ l++; } } } } return res; } } 复杂度 时间复杂度： O ( n l o g n + n 2 ) O(nlogn+n^2) O(nlogn+n2)，其中 n是数组的长度。排序所需的时间复杂度一般为 O ( n l o g n ) O(nlogn) O(nlogn)，查找三元组的时间复杂度为 O ( n 3 ) O(n^3) O(n3)，因此时间复杂度为 O ( n 3 ) O(n^3) O(n3) 空间复杂度： O ( 1 ) O(1) O(1)