2023-11-22
思路:
和之前的一篇博客的思路相同的,都是排序+双指针
只不过多加了一层循环,总时间复杂度为o(n3)
15. 三数之和 - 追梦•少年 - 博客园 (cnblogs.com)
双指针:
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { //2层循环内 双指针 o(n3) List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { // nums[i] > target 直接返回, 剪枝操作 if (nums[i] > 0 && nums[i] > target) { return result; } if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重 continue; } for (int j = i + 1; j < nums.length; j++) { if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重 continue; } int left = j + 1; int right = nums.length - 1; while (right > left) { // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出 long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // 对nums[left]和nums[right]去重 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; left++; right--; } } } } return result; } }